Задан связный неориентированный граф с четным количеством вершин. Граф называется связным, если все его вершины связаны друг с другом ребрами.
Вам следует найти остовное дерево, медиана весов рёбер которого минимальна. Остовное дерево графа включает в себя все его вершины.
Входные данные состоят из нескольких тестов. Формат каждого теста следующий.
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 и не обрабатывается.
Для каждого теста в отдельной строке вывести искомое значение медианы.