Description
The story is just for fun. You can skip it and navigate to the last pragraph and hint directly as you wish.
Palm Islands are renowned artificial islands in Dubai, as well as a world-famous tourist hotspot, which shape is just like a palm, attracting thousands of millions of tourists every year. For the purpose of promoting the development of the tourism industry, Grand Duchy（大公國）of NTHU has also decided to build an artificial island called ''Tree Island''. The whole island consists of \(n\) attractions and \(n-1\) bidirected roads which connect two different attractions. Every two attractions are connected and between which there exists a unique path.
With an eye to developing tourism industry, the authority concerned planned to build some highway. Nevertheless, due to the inadequate budget, the Office of General Affairs resolved to build a highway between two ''second-longest'' attractions. Note that the ''second-longest'' distance means the distance is strictly less than the longest distance.
Hint
Recall the homework of the longest distance (a.k.a. diameter) of a tree. Instead of performing DFS twice, there is a solution to find the diameter in one DFS. For any tree whose root is \(i\), if we have two properties of its subtrees / children (\(j\)): the diameter (denoted by \(d\)) and the longest distance to any leaf (denoted by \(p\)), then we have \(p_i=\displaystyle\max_{\forall j\text{ is a child of }i}(p_j+w_{i,j})\), and \(d_i\) is either in its subtrees: \(\displaystyle\max_{\forall j\text{ is a child of }i}d_j\) or passing through the root: \(p_i+\displaystyle\max_{\forall j'\text{ is a child of }i}(p_{j'}+w_{i,j'})\), where \(j'\) mustn't be the same as we took in \(p_i\). For instance:
In the above digraph, we choose \(0\) to be root. For all internal nodes, \(p_4=18\) and \(d_4=28\); \(p_5=2+18=20\) and \(d_5=\max\{28, 20+10\}=30\); \(p_0=6+20=26\) and \(d_0=\max\{30, 26+8\}=34\).
Hence your task is to extend the above concept to second longest diameter. That is, could you find the relation between the root and its subtrees / children of the four properties: diameter (\(d\)), the second diameter (\(d'\), the answer), the longest distance to any leaf (\(p\)) and the second-longest distance to any leaf (\(p'\))? What are the candidates of \(d_i, d'_i\) and what are the candidates of \(p_i, p'_i\)?
Note that since the tree is a bit large, you may need use a hand-written linked list (or some dynamic-length array) to store the tree.
Input
There are \(n\) lines in each test case. The first line contain an integer \(n < 10^5\) indicating the number of the attractions. The remaining \(n-1 \) lines contains three integers \(u_i, v_i, w_i (0\leq u_i, v_i<n, 0 < w_i < 100)\) which means there is an edge connected \(u_i, v_i\) lengthed \(w_i\).
There are 6 test cases. In the first two ones, \(n < 100\). In another two ones, \(w_i=1\).
Output
Please print out an integer which is the ''second longest'' distance. Remember to put a newline character at the end of line.