There was a civil war between two factions in Skyrim, a province of the Empire on the continent of Tamriel. The
Stormcloaks, led by Ulfric Stormcloak, are made up of Skyrim's native Nord race. Their goal is an independent
Skyrim free from Imperial interference. The Imperial Legion, led by General Tullius, is the military of the Empire
The current target of Ulfric Stormcloak is to attack Whiterun City, which is under controlled by General Tullius.
Near by this city there are N towers under the Empire's control. There are N - 1 roads linking these towers, so
In military affairs, tactical depth means the longest path between two of all towers. Larger the tactical depth is,
more stable these towers are.
Your mission, should you choose to accept it. In each turn, Ulfric tells you two roads. You need to figure out the
tactical depth after destroying these two roads.
The first line of input contains an integer t which is the number of test cases. Then t test cases follow. For each test
case, the first line contains two integers N (N <= 100000), representing the number of towers, and Q (Q <= 100000),
represeting the number of queries.
In the next N - 1 lines, the i-th line describes the i-th road and contains three integers u, v and w (0 <= w <= 5000)
corressponding to a path between u and v of length w .
In the next Q lines, each line contains two integers u and v representing that the u -th road and the v -th road would
be destroyed in this turn. It is guaranteed that u != v .
For each query, output the tactical depth.