记录编号	129012	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]关押罪犯	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2014-10-18 21:30:14	内存使用	1.59 MiB

#include <algorithm>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>

#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("prison1.in", "r");
FILE *out = fopen("prison1.out", "w");
#endif
using namespace std;
inline void getint(int &x){
	char c = fgetc(in);
	while(!isdigit(c)) c = fgetc(in);
	x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 - '0' + c;
}

/*===========================================*/
#define maxn (20005)
#define maxm (100005)
namespace UFS{
	int pre[maxn<<1];
	inline void init(int size){
		int i;
		for(i = 0;i <= size; ++i)
			pre[i] = i;
	}
	int find(int k){
		if(pre[k] == k)return k;
		return pre[k] = find(pre[k]);
	}
}
struct edge{
	int x, y, w;
}E[maxm];
inline bool cmp(const edge&a, const edge&b){return a.w > b.w;}
int n, m;
using namespace UFS;
int main(){
	int i;
	getint(n), getint(m);
	init(n << 1);
	for(i = 0;i < m;++i)
		getint(E[i].x),getint(E[i].y),getint(E[i].w);
	sort(E, E + m, cmp);
	for(i = 0;i < m;++i){
		int x = find(E[i].x), y = find(E[i].y);
		if(x == y){
			fprintf(out, "%d\n", E[i].w);
			return 0;
		}
		pre[x] = find((y - 1 + n) % (n << 1) + 1);
		pre[y] = find((x - 1 + n) % (n << 1) + 1);
	}
	fprintf(out, "0\n");
	return 0;
}