记录编号	206368	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	dashgua	是否通过	通过
代码语言	C++	运行时间	0.106 s
提交时间	2015-11-06 20:58:57	内存使用	5.98 MiB

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>


template<class Num>void read(Num &x)
{
	int flag = 1;
	char c;
	
	while((c = getchar()) < '0' || c > '9')
		if(c == '-') flag *= -1;
	x = c - '0';
	while((c = getchar()) >= '0' && c <= '9')
		x *= 10, x += c - '0';
	x *= flag;		
}
template<class Num>void write(Num x)
{
	static int s[25];
	int sl = 0;
	
	if(!x) putchar('0');
	if(x < 0) putchar('-'), x *= -1;
	
	while(x) s[sl++] = x % 10, x /= 10;
	while(sl--) putchar(s[sl] + '0');
}
const int maxn = 20050, maxm = 1e5 + 20;

int N, M, fa[maxn], G[maxn];
std::pair<int,std::pair<int,int> > edge[maxm];

void init()
{
	int u, v, w;
	
	read(N), read(M);
	
	for(int i = 1; i <= M; i++)
	{
		read(u), read(v), read(w);
		edge[i] = std::make_pair(w, std::make_pair(u, v));
	}
}
int find(int x)
{
	if(x != fa[x])
	{
		find(fa[x]);
		G[x] ^= G[fa[x]];
		fa[x] = fa[fa[x]];
	}
}
int solve()
{
	for(int i = 1; i <= N; i++) fa[i] = i;
	
	std::sort(edge + 1, edge + M + 1);
	
	for(int i = M; i >= 1; i--)
	{
		int u = edge[i].second.first, v = edge[i].second.second;
		
		find(u), find(v);
		
		if(fa[u] == fa[v])
		{
			if((G[u] ^ G[v]) == 0) return edge[i].first;
		}
		else
		{
			G[fa[u]] = G[u] ^ G[v] ^ 1;
			fa[fa[u]] = fa[v];
		}
	}
	
	return 0;
}
int main()
{
	freopen("prison1.in","r",stdin);
	freopen("prison1.out","w",stdout);
	
	init();
	
	write(solve());
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}