The Traveling Salesman Problem (TSP) is a classical problem that we are to find the shortest distance traversing all vertices in a graph from any source and returning to the source, which is considered hard for computers (and maybe human as well).
Nevertheless, the TSP on tree is quite easy: the shortest circuit must visit all edges exactly twice. You could prove this by induction. So let's consider the Open Loop TSP, in which the salesman is not required to return to the source.
In this problem, your task is the Open Loop TSP on trees, i.e., finding the shortest distance traversing all nodes in a tree from any source without returning to the source.
There's an interger \(n\) in the first line, indicating the number of nodes in the tree.
The next \(n-1\) lines consist of three integers \(a_i,b_i,w_i\) representing that there's an bidirected edge between \(a_i\) and \(b_i\) weighing \(w_i<2^{31}\).
For \(50\%\) of the testcases, \(n\leq5\times10^4\). For the other \(50\%\) of the testcases, \(n\leq10^6\).
Please print the shortest distance traversing all nodes in a tree from any source without returning to the source.