记录编号	454710	评测结果	AAAAAAAAAA
题目名称	[福州培训2010] 修复公路	最终得分	100
用户昵称	WHZ0325	是否通过	通过
代码语言	C++	运行时间	0.183 s
提交时间	2017-09-29 15:15:47	内存使用	1.44 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
int fa[1005];
int find(int x) {
	int root=x;
	while(root!=fa[root]) {
		root=fa[root];
	}
	while(fa[x]!=root) {
		int t=fa[x];
		fa[x]=root;
		x=t;
	}
	return root;
}
struct fix {
	int a,b,t;
	bool operator < (const fix &b) const {
		return t<b.t;
	}
} done[100005];
int main() {
	freopen("roada.in","r",stdin);
	freopen("roada.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) {
		fa[i]=i;
	}
	for(int i=0;i<m;i++) {
		scanf("%d%d%d",&done[i].a,&done[i].b,&done[i].t);
	}
	sort(done,done+m);
	int root;
	bool same;
	for(int i=0;i<m;i++) {
		root=fa[find(done[i].a)]=find(done[i].b);
		same=true;
		for(int j=0;j<n;j++) {
			if(find(j)!=root) {
				same=false;
				break;
			}
		}
		if(same) {
			printf("%d\n",done[i].t);
			return 0;
		}
	}
	printf("-1\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}