Hunt
Lord Bradley is on a quest to hunt a yeti, a representative of species considered extinct for millennia, but only recently spotted in the Himalaya mountains. As an unmatched hunter and a lover of all things valuable, he wishes to capture the yeti and add its skin to his extensive collection.
The yeti lives in a cave system beneath the mountains. In a questionably legal manner, Lord Bradley was able to acquire a map of the system, which consists of some caves and tunnels of various lengths joining them. Strangely, the system appears to be connected: every two caves are connected by a path of tunnels. Given his exceptional physical prowess, the veteran voyager plans to push the yeti into a dead end and engage it in melee. To achieve that, he asks you to destroy some of the tunnels so that every two caves are connected by a unique path (the cave graph should become a tree).
Bradley does not wish to track the animal for too long - choose the destroyed tunnels such that the length of the path between the two most distant caves is minimal possible.
Input
The first line contains the number t of test cases. The test cases follow.
The first line of a test case contains two positive integers: n ≤ 500 and m ≤ 5000 - the number of caves and the number of tunnels between them, respectively. Each of the next m lines contains three integers a, b and d (1 ≤ a, b ≤ n, 1 ≤ d ≤ 10^6), which denote a tunnel linking caves a and b, whose length is d.
Output
For each test case, output one line containing the minimum longest distance between two caves after destroying the tunnels (it is quite obvious that exactly m - n + 1 of them must be buried).