#include<bits/stdc++.h>
#define MAX_N 6500000
#define rank Asdfiasofsad
using namespace std;
 
struct edge{
  int c,a,b;
  bool operator < (edge x)const{return c<x.c;}
};
 
int par[MAX_N];
int rank[MAX_N];
int n,m;
edge e[50000];
void init(int n){
  for(int i=0;i<n;i++){
    par[i]=i;
    rank[i]=0;
  }
}
 
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 cal(){
  int c=0;
  init(n);
  for(int i=0;i<m;i++){
    if(same(e[i].a,e[i].b))continue;
    unite(e[i].a,e[i].b);
    if(++c==n/2)return e[i].c;
  }
}
 
int main(){
  while(cin>>n>>m,n){
    for(int i=0;i<m;i++){
      cin>>e[i].a>>e[i].b>>e[i].c;
      e[i].a--,e[i].b--;
    }
    sort(e,e+m);
    cout<<cal()<<endl;
  }
  return 0;
}
### Prompt

Develop a solution in CPP to the problem described below:

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 MAX_N 6500000
#define rank Asdfiasofsad
using namespace std;
 
struct edge{
  int c,a,b;
  bool operator < (edge x)const{return c<x.c;}
};
 
int par[MAX_N];
int rank[MAX_N];
int n,m;
edge e[50000];
void init(int n){
  for(int i=0;i<n;i++){
    par[i]=i;
    rank[i]=0;
  }
}
 
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 cal(){
  int c=0;
  init(n);
  for(int i=0;i<m;i++){
    if(same(e[i].a,e[i].b))continue;
    unite(e[i].a,e[i].b);
    if(++c==n/2)return e[i].c;
  }
}
 
int main(){
  while(cin>>n>>m,n){
    for(int i=0;i<m;i++){
      cin>>e[i].a>>e[i].b>>e[i].c;
      e[i].a--,e[i].b--;
    }
    sort(e,e+m);
    cout<<cal()<<endl;
  }
  return 0;
}
```