#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = 0xfffffff;
const int MAXN = 2010;
const int MAXM = 50010;
struct Edge{
    int u, v, f, nxt;
};
int N, M;
int nume;
int g[MAXN];
Edge e[MAXM];
int fa[MAXN];
void addEdge(int u, int v, int c)
{
    e[++nume].v = v;
    e[nume].u = u;
    e[nume].f = c;
    e[nume].nxt = g[u];
    g[u] = nume;
}

bool cmp(Edge a, Edge b)
{
    return a.f < b.f;
}
int getfather(int x)
{
    if(x == fa[x])
        return x;
    else
        return fa[x] = getfather(fa[x]);
}
int kruscal() {
    vector<int> vec;
    sort(e+1, e+nume+1, cmp);
    int cnt = N;
    for(int i = 1; i <= N; i++)  fa[i] = i;
    for(int i = 1; i <= nume; i++) {
        int t1 = getfather(e[i].u);
        int t2 = getfather(e[i].v);
        if(t1 != t2) {
            fa[t1] = t2;
            cnt--;
            vec.push_back(e[i].f);
            if(cnt==1)
                break;
        }
    }
    //for(int i = 0; i < vec.size(); i++)
    //    cout<<vec[i]<<endl;
    //sort(vec.begin(), vec.end());
    return vec[vec.size()/2];
    //if(vec.)
}
int main()
{
    while(cin>>N>>M&&N&&M) {
        nume = 0;
        memset(g, 0, sizeof(g));
        for(int i = 1; i <= M; i++) {
            int x, y, xy;
            cin>>x>>y>>xy;
            addEdge(x, y, xy);
            addEdge(y, x, xy);
        }
        cout<<kruscal()<<endl;
    }
    return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

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.

Example

Input

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

5
2
421

### Response

```cpp
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = 0xfffffff;
const int MAXN = 2010;
const int MAXM = 50010;
struct Edge{
    int u, v, f, nxt;
};
int N, M;
int nume;
int g[MAXN];
Edge e[MAXM];
int fa[MAXN];
void addEdge(int u, int v, int c)
{
    e[++nume].v = v;
    e[nume].u = u;
    e[nume].f = c;
    e[nume].nxt = g[u];
    g[u] = nume;
}

bool cmp(Edge a, Edge b)
{
    return a.f < b.f;
}
int getfather(int x)
{
    if(x == fa[x])
        return x;
    else
        return fa[x] = getfather(fa[x]);
}
int kruscal() {
    vector<int> vec;
    sort(e+1, e+nume+1, cmp);
    int cnt = N;
    for(int i = 1; i <= N; i++)  fa[i] = i;
    for(int i = 1; i <= nume; i++) {
        int t1 = getfather(e[i].u);
        int t2 = getfather(e[i].v);
        if(t1 != t2) {
            fa[t1] = t2;
            cnt--;
            vec.push_back(e[i].f);
            if(cnt==1)
                break;
        }
    }
    //for(int i = 0; i < vec.size(); i++)
    //    cout<<vec[i]<<endl;
    //sort(vec.begin(), vec.end());
    return vec[vec.size()/2];
    //if(vec.)
}
int main()
{
    while(cin>>N>>M&&N&&M) {
        nume = 0;
        memset(g, 0, sizeof(g));
        for(int i = 1; i <= M; i++) {
            int x, y, xy;
            cin>>x>>y>>xy;
            addEdge(x, y, xy);
            addEdge(y, x, xy);
        }
        cout<<kruscal()<<endl;
    }
    return 0;
}
```