#include<fstream>
#include<algorithm>
using namespace std;
const int N(20001);
const int M(100001);
struct node{ int a,b,c; };
node g[M];
int fri[N],ene[N]={0}; // fri:friend ene:enemy
bool comp(const node &x,const node &y)
{
return x.c>y.c;
}
int f(int x)
{
while (fri[x]!=x) x=fri[x];
return x;
}
void merge(int x,int y)
{
int k1,k2;
k1=f(x);
k2=f(y);
if (k1!=k2)
fri[x]=fri[y]=fri[k2]=k1;
}
int main()
{
ifstream cin("prison.in");
ofstream cout("prison.out");
int n,m,k1,k2,k3,k4;
bool found(false);
cin>>n>>m;
for (int i=0;i<m;i++) cin>>g[i].a>>g[i].b>>g[i].c;
sort(g,g+m,comp);
for (int i=1;i<=n;i++) fri[i]=i;
for (int i=0;i<m;i++)
{
k1=f(g[i].a); k2=f(g[i].b);
if (k1==k2) { cout<<g[i].c<<endl; found=true; break; }
k3=ene[g[i].a]; k4=ene[g[i].b];
if (k3>0) { merge(g[i].b,k3); ene[g[i].a]=f(k3); } else ene[g[i].a]=k2;
if (k4>0) { merge(g[i].a,k4); ene[g[i].b]=f(k4); }else ene[g[i].b]=k1;
}
if (!found) cout<<0<<endl;
//system("pause");
return 0;
}
posted on 2012-06-21 12:17
龙在江湖 阅读(443)
评论(0) 编辑 收藏 引用 所属分类:
竞赛题解_NOIP