Оптимізація мережі тунелів#5549
Експедиція досліджує стародавню печерну систему, нещодавно виявлену в Гімалаях. Система складається з кількох печер, з'єднаних тунелями різної довжини. Дослідники отримали карту, на якій показані всі печери та тунелі. Цікаво, що печерна система зв'язна: до будь-якої пари печер можна дістатися, пройшовши якоюсь послідовністю тунелів.
Щоб проаналізувати структуру, дослідники вирішили спростити мережу, видаливши деякі тунелі так, щоб між кожною парою печер існував рівно один унікальний шлях (тобто система стала деревом). Однак, щоб полегшити пересування печерами, вони хочуть зробити це так, щоб мінімізувати найбільшу відстань між будь-якими двома печерами.
У першому рядку записане число тестових випадків . Далі наведені описи тестових випадків.
Перший рядок кожного тестового випадку містить два натуральних числа: n~(n \le 500) та m~(m \le 5000) — кількість печер і кількість тунелів між ними. Кожен з наступних рядків містить три цілих числа і d~(1 \le a, b \le n,~1 \le d \le 10^6), що описують тунель довжиною між печерами і .
Для кожного тестового випадку в окремому рядку виведіть мінімально можливе значення максимальної відстані між двома печерами після того, як надлишкові тунелі буде знищено (очевидно, що саме m - n + 1 з них треба видалити).
Приклад 1