Median Tree
You are given a connected undirected graph which has even numbers of nodes. A connected graph is a graph in which all nodes are connected directly or indirectly by edges.
Your task is to find a spanning tree whose median value of edges' costs is minimum. A spanning tree of a graph means that a tree which contains all nodes of the graph.
Input
The input consists of multiple datasets.
The format of each dataset is as follows.
n m
s_1 t_1 c_1
...
s_m t_m c_m
The fi rst line contains an even number n (2 ≤ n ≤ 1000) and an integer m (n-1 ≤ m ≤ 10000). n is the nubmer of nodes and m is the number of edges in the graph.
Then m lines follow, each of which contains s_i (1 ≤ s_i ≤ n), t_i (1 ≤ s_i ≤ n, t_i ≠ s_i) and c_i (1 ≤ c_i ≤ 1000).
This means there is an edge between the nodes s_i and t_i and its cost is c_i. There is no more than one edge which connects s_i and t_i.
The input terminates when n = 0 and m = 0. Your program must not output anything for this case.
Output
Print the median value in a line for each dataset.