Alice has a weighted tree of vertices. A tree is a connected acyclic graph with exactly 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 . Then she can move to any adjacent vertex of , 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 denoting the number of vertices in the tree.
The next lines contain 3 space-separated integers , denoting an edge between vertices and of weight .
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
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.
