Медіана дерева
Задано зв'язний неорієнтований граф з парною кількістю вершин. Граф називається зв'язним, якщо усі його вершини зв'язані одна з одною ребрами.
Вам потрібно знайти остовне дерево, мадіана ваг ребер якого мінімальна. Остовне дерево графа включає у себе усі його вершини.
Вхідні дані
Вхідні дані складаються з декількох тестів. Формат кожного тесту нраступний.
n m
s_1 t_1 c_1
...
s_m t_m c_m
Перший рядок містить парне ціле n (2 ≤ n ≤ 1000) - кількість вершин та кількість ребер m (n - 1 ≤ m ≤ 10000) графа. Далі йде m рядків, кожен з яких містить s_i (1 ≤ s_i ≤ n), t_i (1 ≤ s_i ≤ n, t_i ≠ s_i) та c_i (1 ≤ c_i ≤ 1000). Рядок визначає наявність ребра між вершинами s_i та t_i вагою c_i. Існує не більше одного ребра, яке з'єднує s_i та t_i. Останній рядок містить n = 0, m = 0 і не опрацьовується.
Вихідні дані
Для кожного тесту у окремому рядку вивести шукане значення медіани.