Luogu P1525

#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 100010
using namespace std;

int n,m;
int pre[M<<1];
struct node{
	int from,to;
	int anger;
}a[M];

bool cmp(node a,node b){
	return a.anger>b.anger;
}

int find(int x){
	return pre[x]==x?x:pre[x]=find(pre[x]);
}

void Do(int a,int b){
	pre[find(b)]=find(a);
}

int main(){
	while(~scanf("%d%d",&n,&m)){
		for(int i=1;i<=n<<1;i++)
			pre[i]=i;
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].anger);
		sort(a+1,a+n+1,cmp);
		bool flag=0;
		for(int i=1;i<=m;i++){
			if(find(a[i].from)==find(a[i].to)){
				flag=1;
				printf("%d\n",a[i].anger);
				break;
			}
			else{
				Do(a[i].from,a[i].to+n);
				Do(a[i].to,a[i].from+n);
			}
		}	
	}
}