## A Tree Problem 2

View as PDF

Points: 15
Time limit: 2.0s
Memory limit: 128M

Problem type

Marcus has a tree with nodes, numbered through . The edge in this tree connects nodes and and has a length of .

Marcus created a complete graph with nodes. The length of the edge connecting nodes and in this graph is equal to the shortest distance between nodes and 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 .

The next lines will each contain three integers, . 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