#include<bits/stdc++.h>
#define eps 1e-9
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define MAXN 10005
#define MAXM 40005
#define INF 0x3fffffff
#define PB push_back
#define MP make_pair
#define X first
#define Y second
#define clr(x,y) memset(x,y,sizeof(x));
using namespace std;
typedef long long LL;
int i,j,k,n,m,x,y,T,ans,big,cas,num,len;
bool flag;

int edge,head[MAXN];
struct node
{
	int x,y,w;
}p[10005];

bool cmp(node a,node b)
{
	return a.w<b.w;
}

int pre[10005];   //??根?点，起始??pre[i]=i
int find(int u)   //?找u?点??集合的根?点
{
	int r=u;
	while (pre[r]!=r) r=pre[r];  //沿着?向上不断找father，直到找到根?点root (存入r中)
	int i=u,j;
	while (i!=r)   //路径??，即把向上找???的?个?点（重新沿?点向上找一遍），他?的father都??root
	{
		j=pre[i];
		pre[i]=r;
		i=j;
	}
	return r;  //返回根?点的?号
}

int main()
{
	while (scanf("%d%d",&n,&m),n+m)
	{
		memset(head,-1,sizeof(head));
		edge=0;
		for (i=0;i<m;i++)
		{
			scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w);
		}
		sort(p,p+m,cmp);
		for (i=1;i<=n;i++) pre[i]=i;
		int t=n/2;num=0;
		for (i=0;i<m;i++)
		{
			int fx=find(p[i].x);
			int fy=find(p[i].y);
			if (fx!=fy)
			{
				pre[fx]=fy;
				num++;
				if (num==t)
				{
					printf("%d\n",p[i].w);
					break;
				}
			}
		}
		
	}
	
	return 0;
}
### Prompt

Create a solution in Cpp for 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>
#define eps 1e-9
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define MAXN 10005
#define MAXM 40005
#define INF 0x3fffffff
#define PB push_back
#define MP make_pair
#define X first
#define Y second
#define clr(x,y) memset(x,y,sizeof(x));
using namespace std;
typedef long long LL;
int i,j,k,n,m,x,y,T,ans,big,cas,num,len;
bool flag;

int edge,head[MAXN];
struct node
{
	int x,y,w;
}p[10005];

bool cmp(node a,node b)
{
	return a.w<b.w;
}

int pre[10005];   //??根?点，起始??pre[i]=i
int find(int u)   //?找u?点??集合的根?点
{
	int r=u;
	while (pre[r]!=r) r=pre[r];  //沿着?向上不断找father，直到找到根?点root (存入r中)
	int i=u,j;
	while (i!=r)   //路径??，即把向上找???的?个?点（重新沿?点向上找一遍），他?的father都??root
	{
		j=pre[i];
		pre[i]=r;
		i=j;
	}
	return r;  //返回根?点的?号
}

int main()
{
	while (scanf("%d%d",&n,&m),n+m)
	{
		memset(head,-1,sizeof(head));
		edge=0;
		for (i=0;i<m;i++)
		{
			scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w);
		}
		sort(p,p+m,cmp);
		for (i=1;i<=n;i++) pre[i]=i;
		int t=n/2;num=0;
		for (i=0;i<m;i++)
		{
			int fx=find(p[i].x);
			int fy=find(p[i].y);
			if (fx!=fy)
			{
				pre[fx]=fy;
				num++;
				if (num==t)
				{
					printf("%d\n",p[i].w);
					break;
				}
			}
		}
		
	}
	
	return 0;
}
```