Лорд Брэдли отправился на охоту на йети - представителя видов, считающихся вымершими на протяжении тысячелетий, но только недавно замеченных в горах Гималаев. Будучи непревзойденным охотником и любителем всех ценных вещей, он хочет поймать йети чтобы добавить его кожу к своей обширной коллекции. Снежный человек живет в пещерной системе гор. Нелегально Лорд Брэдли смог раздобыть карту системы, состоящую из пещер и тоннелей различной длины, их соединяющих. Как ни странно, но система является связной: каждые две пещеры соединены путем через тоннели. Учитывая свою исключительную отвагу, ветеран путешественник хочет загнать йети в тупик и победить его в ближнем бою. Чтобы добиться этого, он просит Вас уничтожить некоторые тоннели так, чтобы каждые две пещеры были соединены одним путем (граф пещер должен стать деревом). Брэдли не хочет гоняться за животным слишком долго - следует разрушить такие тоннели, чтобы расстояние между двумя наиболее удаленными пещерами было минимальным. \InputFile Первая строка содержит количество тестов \textbf{t}. Далее следуют сами тесты. Первая строка каждого теста содержит два натуральных числа: \textbf{n} (\textbf{n} ≤ \textbf{500}) и \textbf{m} (\textbf{m} ≤ \textbf{5000}) - количество пещер и тоннелей между ними. Каждая из следующих \textbf{m} строк содержит три целых числа \textbf{a}, \textbf{b} и \textbf{d} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{n}, \textbf{1} ≤ \textbf{d} ≤ \textbf{10^6}), описывающих тоннель между пещерами \textbf{a} и \textbf{b} длиной \textbf{d}. \OutputFile Для каждого теста вывести в отдельной строке наименьшее возможное значение наибольшего расстояния между двумя пещерами после разрушения тоннелей (очевидно что в точности \textbf{m} - \textbf{n} + \textbf{1} из них должно быть разрушено).