Alice has a weighted tree of N vertices. A tree is a connected acyclic graph with exactly N−1 edges.
Alice wants to visit all the vertices of the tree by following the edges that connect these vertices. But she wants to do so in minimum time. She can pick any tree vertex as the starting point of her journey. Let’s say her current position is C. Then she can move to any adjacent vertex of C, but it costs her time equal to the weight of the edge. She will continue the above moves until she visits all the vertices.
Calculate the shortest time when Alice can visit all the vertices if she can choose any vertex as her starting point.
Input Format
The first line contains a single integer N denoting the number of vertices in the tree.
The next N−1 lines contain 3 space-separated integers (u,v,w), denoting an edge between vertices u and v of weight w.
Output Format
Print a single integer denoting Alice's shortest time to visit all the vertices if she can choose any vertex as her starting point.
Constraints
1≤N≤2∗105
1≤u,v≤N
1≤w≤104
If the starting point is 1, then the shortest path is 1→2→3→2→4. Time = 1 + 2 + 2 + 3 = 8.
If the starting point is 2, then the shortest path is 2→1→2→3→2→4. Time = 1 + 1 + 2 + 2 + 3 = 9.
If the starting point is 3, then the shortest path is 3→2→1→2→4. Time = 2 + 1 + 1 + 3 = 7.
If the starting point is 4, then the shortest path is 4→2→1→2→3. Time = 3 + 1 + 1 + 2 = 7.
Therefore, the shortest time is 7.
