eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Охота

Охота

Ліміт часу 20 секунд
Ліміт використання пам'яті 64 MiB

Лорд Брэдли отправился на охоту на йети - представителя видов, считающихся вымершими на протяжении тысячелетий, но только недавно замеченных в горах Гималаев. Будучи непревзойденным охотником и любителем всех ценных вещей, он хочет поймать йети чтобы добавить его кожу к своей обширной коллекции.

Снежный человек живет в пещерной системе гор. Нелегально Лорд Брэдли смог раздобыть карту системы, состоящую из пещер и тоннелей различной длины, их соединяющих. Как ни странно, но система является связной: каждые две пещеры соединены путем через тоннели. Учитывая свою исключительную отвагу, ветеран путешественник хочет загнать йети в тупик и победить его в ближнем бою. Чтобы добиться этого, он просит Вас уничтожить некоторые тоннели так, чтобы каждые две пещеры были соединены одним путем (граф пещер должен стать деревом).

Брэдли не хочет гоняться за животным слишком долго - следует разрушить такие тоннели, чтобы расстояние между двумя наиболее удаленными пещерами было минимальным.

Вхідні дані

Первая строка содержит количество тестов t. Далее следуют сами тесты.

Первая строка каждого теста содержит два натуральных числа: n (n500) и m (m5000) - количество пещер и тоннелей между ними. Каждая из следующих m строк содержит три целых числа a, b и d (1a, bn, 1d10^6), описывающих тоннель между пещерами a и b длиной d.

Вихідні дані

Для каждого теста вывести в отдельной строке наименьшее возможное значение наибольшего расстояния между двумя пещерами после разрушения тоннелей (очевидно что в точности m - n + 1 из них должно быть разрушено).

Приклад

Вхідні дані #1
2
4 4
1 2 2
2 3 2
3 4 2
4 1 2
4 5
1 2 2
2 3 2
3 4 2
4 1 2
1 3 3
Вихідні дані #1
6
5
Джерело 2013 Petrozavodsk Winter Training Camp, Jagiellonian University Contest, Січень 25, Задача H