记录编号	234245	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.120 s
提交时间	2016-03-07 16:41:54	内存使用	115.52 MiB

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int father[200001];
int m,n,i,x,y,q,po=0;
inline int QuickRead() 
{
	int ret ;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	ret = ch - '0';
	ch = getchar();
	while (ch >= '0' && ch <= '9')
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	return ret;
}
struct pri{
	int a,b,nu;
}_node[10000001];
bool cmp(pri a,pri b)
{
	return a.nu>b.nu;
}
int find(int x)
{
	if(father[x]!=x)father[x]=find(father[x]);
	return father[x];
}

void unionn(int r1,int r2)
{
	father[r2]=r1;
}
int main()
{
 
   freopen("prison1.in","r",stdin);
  freopen("prison1.out","w",stdout);
   n=QuickRead();
   m=QuickRead();
   for(int i=1;i<40001;i++)
   {
   	 	father[i]=i;
   }
   for(int i=1;i<m+1;i++)
   {
		_node[i].a=QuickRead();
		_node[i].b=QuickRead();
		_node[i].nu=QuickRead();
   }
   sort(_node+1,_node+m+1,cmp);
   int r1,r2;
   for(int i=1;i<m+1;i++)
   {
		r1=find(_node[i].a);
		r2=find(_node[i].b);
		if(r1==r2)
		{
			printf("%d\n",_node[i].nu);
			return 0;
		}
		unionn(find(_node[i].b+n),r1);
		unionn(find(_node[i].a+n),r2);
   }
   printf("0\n");
   return 0;
   
}