403171: GYM101059 F Minimize Tree

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Minimize Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Given a weighted undirected tree of N nodes, rooted at the node 1. You can remove at most 1 edge and add another edge of same weight such that the resulting graph is still a tree. Minimize the sum of distances from node 1 to all other nodes.

Input

The first line contains a single integer N, the size of the tree. Next N - 1 lines contain three space separated integers u, v and w, denoting an edge between the vertices u and v of weight w.

Constraints: 1 ≤ N ≤ 5 × 104, 1 ≤ u, v ≤ N,  - 103 ≤ w ≤ 103

Output

Output a single integer, the minimum sum of distances from node 1 to all other nodes.

ExamplesInput
2
1 2 3
Output
3
Input
4
1 2 61
1 3 -14
3 4 -47
Output
-75

Source/Category

加入题单

上一题 下一题 算法标签: