Tunnel Network Optimization#5549
An expedition is studying an ancient cave system recently discovered in the Himalayas. The system consists of several caves connected by tunnels of various lengths. The researchers have obtained a map showing all the caves and tunnels. Curiously, the cave system is connected: every pair of caves can be reached by traversing some sequence of tunnels.
To analyze the structure, the researchers decide to simplify the network by removing certain tunnels so that exactly one unique path exists between every pair of caves (that is, the system becomes a tree). However, to facilitate easier travel through the caves, they wish to do so in a way that minimizes the longest distance between any two caves.
The first line contains the number of test cases . The descriptions of the test cases follow.
The first line of each test case contains two natural numbers: n~(n \le 500) and m~(m \le 5000) — the number of caves and the number of tunnels between them. Each of the following lines contains three integers , and d~(1 \le a, b \le n,~1 \le d \le 10^6), describing a tunnel of length between caves and .
For each test case, output in a separate line the minimal possible value of the maximum distance between two caves after the redundant tunnels have been destroyed (obviously, exactly m - n + 1 of them must be removed).
Example 1