Marcus has a tree with ~N~ nodes, numbered ~1~ through ~N~. The ~i^\text{th}~ edge in this tree connects nodes ~a_i~ and ~b_i~ and has a length of ~c_i~.

Marcus created a complete graph with ~N~ nodes. The length of the edge connecting nodes ~u~ and ~v~ in this graph is equal to the shortest distance between nodes ~u~ and ~v~ in the tree described above.

Marcus would like to know the length of the longest Hamiltonian path in this complete graph. Find the length of that path. A Hamiltonian path in a graph is a path in the graph that visits each node exactly once.

Input Specification

The first line will contain the integer ~N~ ~(2 \le N \le 10^5)~.

The next ~N-1~ lines will each contain three integers, ~a_i, b_i, c_i~ ~(1 \le a_i, b_i \le N, 1 \le c_i \le 10^8)~. The edges are guaranteed to form a tree.

Output Specification

Print the length of the longest Hamiltonian path in the complete graph.

Sample Input 1

5
1 2 5
3 4 7
2 3 3
2 5 2

Sample Output 1

38

Sample Input 2

8
2 8 8
1 5 1
4 8 2
2 5 4
3 8 6
6 8 9
2 7 12

Sample Output 2

132