Time Limit: 20 sec / Memory Limit: 256 MB
Problem Statement
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 first line contains an even number n (2 \leq n \leq 1,000) and an integer m (n-1 \leq m \leq 10,000). 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 \leq s_i \leq n), t_i (1 \leq s_i \leq n, t_i \neq s_i) and c_i (1 \leq c_i \leq 1,000). 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.
Sample Input
Sorry, update sample3 dataset.(11:33)2 1 1 2 5 4 6 1 2 1 1 3 2 1 4 3 2 3 4 2 4 5 3 4 6 8 17 1 4 767 3 1 609 8 3 426 6 5 972 8 1 607 6 4 51 5 1 683 3 6 451 3 4 630 8 7 912 3 7 43 4 7 421 3 5 582 8 4 538 5 7 832 1 6 345 8 2 608 0 0
Output for the Sample Input
5 2 421