Полювання
Лорд Бредлі вирушив на полювання на йєті — істоту, яку вважали вимерлою протягом тисячоліть, але нещодавно помічену в Гімалаях. Як досвідчений мисливець і колекціонер рідкісних речей, він прагне зловити йєті, щоб додати його шкіру до своєї колекції.
Снігова людина мешкає в системі печер у горах. Лорд Бредлі нелегально здобув карту цієї системи, що складається з печер і тунелів різної довжини, які їх з'єднують. Дивно, але система є зв'язною: кожна пара печер з'єднана шляхом через тунелі. Завдяки своїй відвазі, Бредлі хоче загнати йєті в глухий кут і перемогти його в ближньому бою. Для цього він просить вас знищити деякі тунелі так, щоб кожна пара печер була з'єднана лише одним шляхом (граф печер має стати деревом).
Бредлі не бажає довго переслідувати звіра, тому потрібно зруйнувати такі тунелі, щоб відстань між двома найбільш віддаленими печерами була мінімальною.
Вхідні дані
Перший рядок містить кількість тестів t. Далі йдуть самі тести.
Перший рядок кожного тесту містить два натуральних числа: n (n ≤ 500) і m (m ≤ 5000) — кількість печер і тунелів між ними. Кожен з наступних m рядків містить три цілі числа a, b і d (1 ≤ a, b ≤ n, 1 ≤ d ≤ 10^6), що описують тунель між печерами a і b довжиною d.
Вихідні дані
Для кожного тесту виведіть в окремому рядку найменше можливе значення найбільшої відстані між двома печерами після руйнування тунелів (очевидно, що рівно m - n + 1 з них має бути зруйновано).