Медіана дерева#4293
Вам дано зв'язний неорієнтований граф з парною кількістю вершин. Зв'язний граф — це граф, у якому всі вершини з'єднані ребрами (безпосередньо або опосередковано).
Ваше завдання — знайти остовне дерево, медіана вартостей ребер якого є мінімальною. Остовне дерево графа — це дерево, що містить усі вершини графа.
Вхід складається з кількох наборів даних.
Формат кожного набору такий:
s_1\ t_1\ c_1
s_m\ t_m\ c_m
У першому рядку задано парне число (2 \leq n \leq 1000) та ціле число (n-1 \leq m \leq 10000). — кількість вершин, — кількість ребер у графі.
Далі йде рядків; у кожному з них наведено s_i (1 \leq s_i \leq n), t_i (1 \leq t_i \leq n, t_i \neq s_i), c_i (1 \leq c_i \leq 1000).
Це означає, що існує ребро між вершинами s_i і t_i з вартістю c_i. Не існує більше, ніж одного ребра, що з'єднує s_i та t_i.
Вхід завершується, коли n = 0 та m = 0. Для цього випадку програма не повинна нічого виводити.
Для кожного набору даних виведіть в окремому рядку медіанне значення.
Приклад 1