#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,v) for (int i = 0; i < v.size(); i++)
#define RREPALL(i,v) for (int i = v.size()-1; i >= 0; i--)
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(v.begin(), v.end())
#define MIN_ELEMENT(v) min_element(v.begin(), v.end())
#define MAX_ELEMENT(v) max_element(v.begin(), v.end())
#define COUNT(v,n) count(v.begin(), v.end(), n)
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

//蟻本，螺旋本参考
//DisjointSet
//整数配列に対応
class UnionFindTree {
public:
    vector<int> rank, p;

    UnionFindTree() {}

    UnionFindTree(int size) {
        rank.resize(size, 0);
        p.resize(size, 0);
        for (int i = 0; i < size; ++i) {
            makeSet(i);
        }
    }

    void makeSet(int x)
    {
        p[x] = x;
        rank[x] = 0;
    }

    bool same(int x, int y)
    {
        return findSet(x) == findSet(y);
    }

    void unite(int x, int y)
    {
        link(findSet(x), findSet(y));
    }

    void link(int x, int y)
    {
        if (rank[x] > rank[y]) {
            p[y] = x;
        } else {
            p[x] = y;
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
    }

    int findSet(int x)
    {
        if (x != p[x]) {
            p[x] = findSet(p[x]);
        }
        return p[x];
    }

    int maxUnion()
    {
        int size = p.size();
        int r = 0;
        REP(i,size) {
            r = max(r, (int)count(p.begin(), p.end(), i));
        }
        return r;
    }
};

int n, m;
vector<bool> used;
multimap<int, pair<int, int>> d;

void solve()
{
    int cnt = 0;
    used.resize(n, false);
    UnionFindTree uf(n);
    REP(i,m) {
        int s, t, c;
        cin>>s>>t>>c;
        d.insert({c, {s-1, t-1}});
    }

    for (auto itr : d) {
        //cout<<"_"<<itr.first<<"_"<<itr.second.first<<","<<itr.second.second<<endl;
        if (!uf.same(itr.second.first,itr.second.second)) {
            uf.unite(itr.second.first,itr.second.second);
            cnt++;
        }

        if (cnt == n / 2) {
            cout<<itr.first<<endl;
            d.clear();
            return;
        }
    }
}

int main()
{
    while (cin>>n>>m, n != 0) {
        solve();
    }

    return 0;
}


### Prompt

In CPP, your task is to solve the following problem:

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 <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,v) for (int i = 0; i < v.size(); i++)
#define RREPALL(i,v) for (int i = v.size()-1; i >= 0; i--)
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(v.begin(), v.end())
#define MIN_ELEMENT(v) min_element(v.begin(), v.end())
#define MAX_ELEMENT(v) max_element(v.begin(), v.end())
#define COUNT(v,n) count(v.begin(), v.end(), n)
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

//蟻本，螺旋本参考
//DisjointSet
//整数配列に対応
class UnionFindTree {
public:
    vector<int> rank, p;

    UnionFindTree() {}

    UnionFindTree(int size) {
        rank.resize(size, 0);
        p.resize(size, 0);
        for (int i = 0; i < size; ++i) {
            makeSet(i);
        }
    }

    void makeSet(int x)
    {
        p[x] = x;
        rank[x] = 0;
    }

    bool same(int x, int y)
    {
        return findSet(x) == findSet(y);
    }

    void unite(int x, int y)
    {
        link(findSet(x), findSet(y));
    }

    void link(int x, int y)
    {
        if (rank[x] > rank[y]) {
            p[y] = x;
        } else {
            p[x] = y;
            if (rank[x] == rank[y]) {
                rank[y]++;
            }
        }
    }

    int findSet(int x)
    {
        if (x != p[x]) {
            p[x] = findSet(p[x]);
        }
        return p[x];
    }

    int maxUnion()
    {
        int size = p.size();
        int r = 0;
        REP(i,size) {
            r = max(r, (int)count(p.begin(), p.end(), i));
        }
        return r;
    }
};

int n, m;
vector<bool> used;
multimap<int, pair<int, int>> d;

void solve()
{
    int cnt = 0;
    used.resize(n, false);
    UnionFindTree uf(n);
    REP(i,m) {
        int s, t, c;
        cin>>s>>t>>c;
        d.insert({c, {s-1, t-1}});
    }

    for (auto itr : d) {
        //cout<<"_"<<itr.first<<"_"<<itr.second.first<<","<<itr.second.second<<endl;
        if (!uf.same(itr.second.first,itr.second.second)) {
            uf.unite(itr.second.first,itr.second.second);
            cnt++;
        }

        if (cnt == n / 2) {
            cout<<itr.first<<endl;
            d.clear();
            return;
        }
    }
}

int main()
{
    while (cin>>n>>m, n != 0) {
        solve();
    }

    return 0;
}


```