ABC company is doing a research to turn one of their ~n~ warehouses into a distribution center. These warehouses are connected by ~n-1~ path (connected to other warehouses). Each path has a length. Your task is to find that distribution center so that the total length from the center to other warehouses is minimum.

Input

• The first line contains the number of warehouses ~n~ ~(1 ≤ n ≤ 10^5)~
• Each of the next ~n-1~ lines contains ~3~ integers: ~u, v~ representing an edge between ~u~ and ~v~ ~(0 ≤ u,v ≤ n)~ and ~l~ representing length of ~u,v~ ~(l ≤ 10^5)~.

Output

• Print out a the minimum total length.

Sample Input

5 
0 1 5
1 2 1
2 3 3
1 4 2

Sample Output

12