#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<58;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

class union_find{
	private:
	vector<int> parent,rank;
	int size;
	public:
    int cnt;

    union_find()=default;
    union_find(int n){ init(n); }

    void init(int n){
		size=n;
		cnt=n;
		parent.resize(size);
		rank.resize(size);
		for(int i=0; i<size; ++i){
			parent[i]=i;
			rank[i]=0;
		}
	}

	int find(int x){
		if(parent[x]==x) return x;
		else return parent[x]=find(parent[x]);
	}

	void unite(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y]){
			parent[x]=y;
		} else {
			parent[y]=x;
			if(rank[x]==rank[y]) ++rank[x];
		}
		--cnt;
	}

	bool is_same(int x,int y){
		return find(x)==find(y);
	}
};

struct edge{
    int s,t,c;
    edge(int s,int t,int c):s(s),t(t),c(c){}
    bool operator<(const edge& other)const{ return c<other.c; }
};

void solve(){
    while(true){
        int n,m;
        cin >> n >> m;
        if(n==0 and m==0) break;
        vector<edge> edges;
        rep(i,0,m){
            int s,t,c;
            cin >> s >> t >> c;
            --s;
            --t;
            edges.emplace_back(edge(s,t,c));
        }
        sort(edges.begin(),edges.end());
        union_find uf(n);
        vector<int> costs;
        for(const auto& e:edges) if(!uf.is_same(e.s,e.t)){
            uf.unite(e.s,e.t);
            costs.emplace_back(e.c);
        }
        cout << costs[max(0,(n-2)/2)] << endl;
    }
}


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cout << fixed << setprecision(8);
    solve();
    return 0;
}
### Prompt

Your task is to create a Cpp solution to 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 rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define dump(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define dump(x)
#endif

typedef long long int ll;
typedef pair<int,int> pii;
//template<typename T> using vec=std::vector<T>;

const int inf=1<<30;
const long long int infll=1LL<<58;
const double eps=1e-9;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

class union_find{
	private:
	vector<int> parent,rank;
	int size;
	public:
    int cnt;

    union_find()=default;
    union_find(int n){ init(n); }

    void init(int n){
		size=n;
		cnt=n;
		parent.resize(size);
		rank.resize(size);
		for(int i=0; i<size; ++i){
			parent[i]=i;
			rank[i]=0;
		}
	}

	int find(int x){
		if(parent[x]==x) return x;
		else return parent[x]=find(parent[x]);
	}

	void unite(int x,int y){
		x=find(x);
		y=find(y);
		if(x==y) return;
		if(rank[x]<rank[y]){
			parent[x]=y;
		} else {
			parent[y]=x;
			if(rank[x]==rank[y]) ++rank[x];
		}
		--cnt;
	}

	bool is_same(int x,int y){
		return find(x)==find(y);
	}
};

struct edge{
    int s,t,c;
    edge(int s,int t,int c):s(s),t(t),c(c){}
    bool operator<(const edge& other)const{ return c<other.c; }
};

void solve(){
    while(true){
        int n,m;
        cin >> n >> m;
        if(n==0 and m==0) break;
        vector<edge> edges;
        rep(i,0,m){
            int s,t,c;
            cin >> s >> t >> c;
            --s;
            --t;
            edges.emplace_back(edge(s,t,c));
        }
        sort(edges.begin(),edges.end());
        union_find uf(n);
        vector<int> costs;
        for(const auto& e:edges) if(!uf.is_same(e.s,e.t)){
            uf.unite(e.s,e.t);
            costs.emplace_back(e.c);
        }
        cout << costs[max(0,(n-2)/2)] << endl;
    }
}


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cout << fixed << setprecision(8);
    solve();
    return 0;
}
```