#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

class UnionFindTree{
private:
  int* mParent;
  int* mRank;
  int mSize;

public:
  UnionFindTree(int n){
    mSize = n;
    mParent = new int[n];
    mRank = new int[n];

    for(int i=0; i < n; i++){
      mParent[i] = i;
      mRank[i] = 0;
    }
  }

  ~UnionFindTree(){
    delete[] mParent;
    delete[] mRank;
  }

  bool same(int lhs,int rhs){
    return (find(lhs) == find(rhs) ? true : false);
  }

  int find(int pos){
    if(pos == mParent[pos]) return pos;
    return find(mParent[pos]);
  }
  
  void unite(int lhs,int rhs){
    lhs = find(lhs);
    rhs = find(rhs);
    
    if(lhs == rhs) return;
    
    if(mRank[lhs] > mRank[rhs]){
      mParent[lhs] = rhs;
      mRank[rhs] += mRank[lhs];
      mRank[lhs] = 0;
    }
    else{
      mParent[rhs] = lhs;
      mRank[lhs] += mRank[rhs];
      mRank[rhs] = 0;
    }
  }

  int size() const{
    return mSize;
  }
};

class State{
public:
  int from;
  int to;
  int cost;
  State(int _f,int _t,int _c) :
    from(_f), to(_t), cost(_c) {}
  bool operator<(const State& s) const{
    return cost < s.cost;
  }
  bool operator>(const State& s) const{
    return cost > s.cost;
  }
};

int main(){
  int num_of_nodes;
  int num_of_edges;
  while(~scanf("%d %d",&num_of_nodes,&num_of_edges)){
    if(num_of_nodes == 0 && num_of_edges == 0) break;

    priority_queue<State,vector<State>,greater<State> > que;
    for(int edge_idx = 0; edge_idx < num_of_edges; edge_idx++){
      int from,to,cost;
      scanf("%d %d %d",&from,&to,&cost);
      from--; to--;
      que.push(State(from,to,cost));
    }

    UnionFindTree uft(num_of_nodes);

    vector<int> log;
    while(!que.empty()){
      State s = que.top();
      que.pop();
      if(!uft.same(s.from,s.to)){
        uft.unite(s.from,s.to);
        log.push_back(s.cost);
      }
    }

    printf("%d\n",log[log.size()/2]);
  }
}
### 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
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;
  
static const int tx[] = {0,1,0,-1};
static const int ty[] = {-1,0,1,0};

class UnionFindTree{
private:
  int* mParent;
  int* mRank;
  int mSize;

public:
  UnionFindTree(int n){
    mSize = n;
    mParent = new int[n];
    mRank = new int[n];

    for(int i=0; i < n; i++){
      mParent[i] = i;
      mRank[i] = 0;
    }
  }

  ~UnionFindTree(){
    delete[] mParent;
    delete[] mRank;
  }

  bool same(int lhs,int rhs){
    return (find(lhs) == find(rhs) ? true : false);
  }

  int find(int pos){
    if(pos == mParent[pos]) return pos;
    return find(mParent[pos]);
  }
  
  void unite(int lhs,int rhs){
    lhs = find(lhs);
    rhs = find(rhs);
    
    if(lhs == rhs) return;
    
    if(mRank[lhs] > mRank[rhs]){
      mParent[lhs] = rhs;
      mRank[rhs] += mRank[lhs];
      mRank[lhs] = 0;
    }
    else{
      mParent[rhs] = lhs;
      mRank[lhs] += mRank[rhs];
      mRank[rhs] = 0;
    }
  }

  int size() const{
    return mSize;
  }
};

class State{
public:
  int from;
  int to;
  int cost;
  State(int _f,int _t,int _c) :
    from(_f), to(_t), cost(_c) {}
  bool operator<(const State& s) const{
    return cost < s.cost;
  }
  bool operator>(const State& s) const{
    return cost > s.cost;
  }
};

int main(){
  int num_of_nodes;
  int num_of_edges;
  while(~scanf("%d %d",&num_of_nodes,&num_of_edges)){
    if(num_of_nodes == 0 && num_of_edges == 0) break;

    priority_queue<State,vector<State>,greater<State> > que;
    for(int edge_idx = 0; edge_idx < num_of_edges; edge_idx++){
      int from,to,cost;
      scanf("%d %d %d",&from,&to,&cost);
      from--; to--;
      que.push(State(from,to,cost));
    }

    UnionFindTree uft(num_of_nodes);

    vector<int> log;
    while(!que.empty()){
      State s = que.top();
      que.pop();
      if(!uft.same(s.from,s.to)){
        uft.unite(s.from,s.to);
        log.push_back(s.cost);
      }
    }

    printf("%d\n",log[log.size()/2]);
  }
}
```