//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>
#include <tuple>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

class UnionFind{
private:
  vector<int> par, rank;
public:
  UnionFind(int n){
	par.assign(n, 0);
	rank.assign(n, 0);
	for(int i=0;i<n;++i)
	  par[i] = i;
  }

  //find root of x
  int find(int x){
	if(par[x] == x)
	  return x;
	return (par[x] = find(par[x]));
  }

  void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(rank[x] < rank[y])
	  par[x] = y;
	else{
	  par[y] = x;
	  if(rank[x] == rank[y])
		++rank[x];
	}
  }

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

int N, M;
vector<tuple<int,int,int>> es;

bool check(int idx){
  int H = (N - 2) / 2;
  if(idx < H || M - idx - 1 < H)
	return false;
	   
  UnionFind uf1(N);
  REP(i,idx+1)
	uf1.unite(get<1>(es[i]), get<2>(es[i]));
  VI edges;
  FOR(i,idx+1,M){
	int s, t, c;
	tie(c,s,t) = es[i];
	if(uf1.same(s, t)) continue;
	uf1.unite(s, t);
	edges.PB(i);
  }

  bool ok = true;
  REP(i,N) if(!uf1.same(i,0)) ok = false;
  if(SZ(edges) > H || !ok)
	return false;

  UnionFind uf2(N);
  uf2.unite(get<1>(es[idx]), get<2>(es[idx]));
  REP(i,SZ(edges)){
	int s, t, c;
	tie(c,s,t) = es[edges[i]];
	uf2.unite(s,t);
  }
  for(int i=idx+1;i<M&&SZ(edges)<H;++i){
	int s, t, c;
	tie(c,s,t) = es[i];
	if(uf2.same(s,t)) continue;
	uf2.unite(s,t);
	edges.PB(i);
  }
  if(SZ(edges) != H)
	return false;

  REP(i,idx){
	int s, t, c;
	tie(c,s,t) = es[i];
	if(uf2.same(s,t)) continue;
	uf2.unite(s,t);
  }

  ok = true;
  REP(i,N) if(!uf2.same(i,0)) ok = false;
  return ok;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  while(cin>>N>>M,N){
	es.assign(M, tuple<int,int,int>());
	REP(i,M){
	  cin >> get<1>(es[i]) >> get<2>(es[i]) >> get<0>(es[i]);
	  get<1>(es[i])--;
	  get<2>(es[i])--;
	}
	SORT(es);

	for(int i=0;i<M;++i){
	  if(check(i)){
		cout << get<0>(es[i]) << endl;
		break;
	  }
	}
  }
  
  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
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>
#include <tuple>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

class UnionFind{
private:
  vector<int> par, rank;
public:
  UnionFind(int n){
	par.assign(n, 0);
	rank.assign(n, 0);
	for(int i=0;i<n;++i)
	  par[i] = i;
  }

  //find root of x
  int find(int x){
	if(par[x] == x)
	  return x;
	return (par[x] = find(par[x]));
  }

  void unite(int x, int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(rank[x] < rank[y])
	  par[x] = y;
	else{
	  par[y] = x;
	  if(rank[x] == rank[y])
		++rank[x];
	}
  }

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

int N, M;
vector<tuple<int,int,int>> es;

bool check(int idx){
  int H = (N - 2) / 2;
  if(idx < H || M - idx - 1 < H)
	return false;
	   
  UnionFind uf1(N);
  REP(i,idx+1)
	uf1.unite(get<1>(es[i]), get<2>(es[i]));
  VI edges;
  FOR(i,idx+1,M){
	int s, t, c;
	tie(c,s,t) = es[i];
	if(uf1.same(s, t)) continue;
	uf1.unite(s, t);
	edges.PB(i);
  }

  bool ok = true;
  REP(i,N) if(!uf1.same(i,0)) ok = false;
  if(SZ(edges) > H || !ok)
	return false;

  UnionFind uf2(N);
  uf2.unite(get<1>(es[idx]), get<2>(es[idx]));
  REP(i,SZ(edges)){
	int s, t, c;
	tie(c,s,t) = es[edges[i]];
	uf2.unite(s,t);
  }
  for(int i=idx+1;i<M&&SZ(edges)<H;++i){
	int s, t, c;
	tie(c,s,t) = es[i];
	if(uf2.same(s,t)) continue;
	uf2.unite(s,t);
	edges.PB(i);
  }
  if(SZ(edges) != H)
	return false;

  REP(i,idx){
	int s, t, c;
	tie(c,s,t) = es[i];
	if(uf2.same(s,t)) continue;
	uf2.unite(s,t);
  }

  ok = true;
  REP(i,N) if(!uf2.same(i,0)) ok = false;
  return ok;
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  while(cin>>N>>M,N){
	es.assign(M, tuple<int,int,int>());
	REP(i,M){
	  cin >> get<1>(es[i]) >> get<2>(es[i]) >> get<0>(es[i]);
	  get<1>(es[i])--;
	  get<2>(es[i])--;
	}
	SORT(es);

	for(int i=0;i<M;++i){
	  if(check(i)){
		cout << get<0>(es[i]) << endl;
		break;
	  }
	}
  }
  
  return 0;
}
```