P5234 [JSOI2012] 越狱老虎桥

#include<bits/stdc++.h>
using namespace std;
#ifdef ONLINE_JUDGE
char buf[1 << 23] , * p1 = buf , * p2 = buf , obuf[1 << 23] , * O = obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int rd() {
	int x = 0 , f = 1;char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1;ch = getchar(); }
	while (isdigit(ch)) x = x * 10 + (ch ^ 48) , ch = getchar();
	return x * f;
}
const int N=5e5+9;
struct pi{
	int fi,se,th;
};
vector<pi>ve[N];
vector<pair<int,int> >rv[N];
int dfn[N],low[N],no,dcc,sy[N],high[N],a;
stack<int> st;
inline void dfs(int x,int fl){
	low[x]=dfn[x]=no=-~no;
	st.push(x);
	for(auto i:ve[x]){
		if(fl==i.th)continue;
		if(!dfn[i.fi]){
			dfs(i.fi,i.th);
			low[x]=min(low[x],low[i.fi]);
		}else low[x]=min(low[x],dfn[i.fi]);
	}
	if(dfn[x]==low[x]){
		dcc=-~dcc;
		int y;
		do{
			y=st.top();
			st.pop();
			sy[y]=dcc;
		}while(y^x);
	}
}
inline void dfs1(int x,int fa,int nm){
	for(auto i:rv[x]){
		if(i.first==fa)continue;
		high[i.first]=high[x];
		if(i.second<=nm) high[i.first]++;
		dfs1(i.first,x,nm);
	}
}
inline bool ck(int x){
	int sl=0;
	for(int i=1;i<=dcc;i=-~i){
		for(auto j:rv[i]){
			if(j.second<=x)sl=-~sl;
		}
	}
	sl>>=1;
	for(int i=1;i<=a;i=-~i) high[i]=0;
	dfs1(1,1,x);
	int ma=0;
	for(int i=1;i<=a;i=-~i){
		if(high[i]>high[ma])ma=i;
	}
	for(int i=1;i<=a;i=-~i) high[i]=0;
	dfs1(ma,ma,x);
	ma=0;
	for(int i=1;i<=a;i=-~i) ma=max(ma,high[i]);
	return ma!=sl;
}
int main(){
	ios::sync_with_stdio(0);
	int b;
	a=rd(),b=rd();
	for(int i=1,x,y,z;i<=b;i=-~i){
		x=rd(),y=rd(),z=rd();
		ve[x].push_back({y,z,i});
		ve[y].push_back({x,z,i});
	}
	for(int i=1;i<=a;i=-~i){
		if(!dfn[i])dfs(i,0);
	}
	for(int i=1;i<=a;i=-~i){
		for(auto j:ve[i]){
			if(sy[i]==sy[j.fi])continue;
			rv[sy[i]].push_back({sy[j.fi],j.se});
		}
	}
	int l=0,r=1e5,zj;
	while(r>=l){
		zj=(l+r)>>1;
		if(ck(zj)) r=~-zj;
		else l=-~zj;
	}
	if(!ck(1e9))cout<<-1;
	else cout<<l;
	return 0;
}