Problems
Longest path in a tree
Longest path in a tree
Undirected weighted tree is given. Find the length of the longest path. Find two vertices the distance between which is maximum.
Input data
The first line contains the number of vertices in the tree n\:(2 \le n \le 10^5). The next n - 1 lines describe the edges. Each line contains three integers: numbers of vertices connected with an edge (vertices are numbered from 1 to n) and the weight w\:(1 \le w \le 10^5) of an edge.
Output data
Print the length of the longest path.
Examples
Input example #1
6 1 2 3 2 3 4 2 6 2 6 4 6 6 5 5
Output example #1
12