记录编号	387966	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	L_in	是否通过	通过
代码语言	C++	运行时间	0.189 s
提交时间	2017-03-28 07:56:36	内存使用	3.14 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 20010
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=10*x+ch-'0',ch=getchar();
	return x*f;
}
int n,m,M;
int v[100000];
struct Edge{
	int to,next,w;
}e[200010];
int head[maxn],tot;
void add(int from,int to,int w){
	e[++tot].w=w;
	e[tot].to=to;
	e[tot].next=head[from];
	head[from]=tot;
}
int col[maxn];
bool dfs(int x){
	for(int i=head[x];i;i=e[i].next){
		if(e[i].w<=M)continue;
		int to=e[i].to;
		if(col[to]==col[x])return false;
		if(!col[to]){
			col[to]=3-col[x];
			if(!dfs(to))return false;
		}
	}return true;
}
bool check(){
	memset(col,0,sizeof col);
	for(int i=1;i<=n;i++){
		if(!col[i]){
			col[i]=1;
			if(!dfs(i))return false;
		}
	}return true;
}
int main(){
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
	n=read();m=read();
	int x,y;
	for(int i=1;i<=m;i++){
		x=read();y=read();v[i]=read();
		add(x,y,v[i]);add(y,x,v[i]);
	}
	sort(v+1,v+m+1);
	int l=1,r=m,mid;
	while(l<=r){
		mid=(l+r)>>1;M=v[mid];
		if(check())r=mid-1;
		else l=mid+1;
	}
	if(r==0)puts("0");
	else printf("%d\n",v[r+1]);
	fclose(stdin);fclose(stdout);
	return 0;
}