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. \InputFile The first line contains the number \textbf{t} of test cases. The test cases follow. The first line of a test case contains two positive integers: \textbf{n} ≤ \textbf{500} and \textbf{m} ≤ \textbf{5000} - the number of caves and the number of tunnels between them, respectively. Each of the next \textbf{m} lines contains three integers \textbf{a}, \textbf{b} and \textbf{d} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{n}, \textbf{1} ≤ \textbf{d} ≤ \textbf{10^6}), which denote a tunnel linking caves \textbf{a} and \textbf{b}, whose length is \textbf{d}. \OutputFile 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 \textbf{m} - \textbf{n} + \textbf{1} of them must be buried).