| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 (추가 시간 없음) | 256 MB | 105 | 85 | 76 | 81.720% |
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.
The input consists of multiple datasets.
The format of each dataset is as follows.
n m s1 t1 c1 ... sm tm cm
The first line contains an even number n (2 ≤ n ≤ 1,000) and an integer m (n-1 ≤ m ≤ 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 si (1 ≤ si ≤ n), ti (1 ≤ si ≤ n, ti ≤ si) and ci (1 ≤ ci ≤ 1,000). This means there is an edge between the nodes si and ti and its cost is ci. There is no more than one edge which connects si and ti.
The input terminates when n=0 and m=0. Your program must not output anything for this case.
Print the median value in a line for each dataset.
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
5 2 421