P5234 越狱老虎桥，落谷过了，但是校内OJ太慢了，得再卡一卡，拜托，谢谢

#include <stdio.h>
using namespace std;
struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x>='0'&&x<='9')
	char buf[MAXSIZE], *p1, *p2;
	char pbuf[MAXSIZE], *pp;
	IO():p1(buf),p2(buf),pp(pbuf) {}
	char gc() {
		if(p1==p2) {
			p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin);
		}
		return p1==p2?' ':*p1++;
	}
	bool blank(const char& ch) {
		return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
	}
	template <class T>
	void read(T &x) {
		x=0;
		char ch=gc();
		while(!isdigit(ch)) {
			ch=gc();
		}
		while(isdigit(ch)) {
			x=(x<<3)+(x<<1)+(ch^48);
			ch=gc();
		}
	}
	void read(char *s) {
		char ch=gc();
		while(blank(ch)) {
			ch=gc();
		}
		while(!blank(ch)) {
			*s++=ch;
			ch=gc();
		}
		*s=0;
	}
	void read(char &ch) {
		ch=gc();
		while(blank(ch)) {
			ch=gc();
		}
	}
} io;
const int N=5e5+5,M=2e6+5;
int n,m,B[M];
int en[M],ne[M],h[N],cnt;
inline void add(const int& a,const int& b) {
	en[++cnt]=b;
	ne[cnt]=h[a];
	h[a]=cnt;
}
int en_[M],ne_[M],h_[N],cnt_;
inline void add_(const int& a,const int& b) {
	en_[++cnt_]=b;
	ne_[cnt_]=h_[a];
	h_[a]=cnt_;
}
int dfn[N],low[N],tot;
int s[N],top;
int bcc_cnt,id[N];
bool tj(const int& x,const int& dad) {
	dfn[x]=low[x]=++tot;
	s[++top]=x;
	for(register int i=h[x]; i; i=ne[i]) {
		!dfn[en[i]]?(tj(en[i],x),low[en[i]]<low[x]&&(low[x]=low[en[i]])):(en[i]!=dad?dfn[en[i]]<low[x]&&(low[x]=dfn[en[i]]):1);
	}
	if(dfn[x]==low[x]) {
		bcc_cnt++;
		int y=0;
		do {
			y=s[top--];
			id[y]=bcc_cnt;
		} while(y!=x);
	}
	return 1;
}
int dis[N],key[M];
bool le[M];
bool dfs(const int& x,const int& dad) {
	for(register int i=h_[x]; i; i=ne_[i]) {
		en_[i]!=dad&&(dis[en_[i]]=dis[x]+le[i],dfs(en_[i],x));
	}
	return 1;
}
inline bool check(const int& x) {
	int num=0;
	B[0]=x+1;
	for(register int i=1; i<=cnt_; i+=4) {
		B[key[i]]<=x?(le[i]=1,num=-~num):(le[i]=0);
		B[key[i+1]]<=x?(le[i+1]=1,num=-~num):(le[i+1]=0);
		B[key[i+2]]<=x?(le[i+2]=1,num=-~num):(le[i+2]=0);
		B[key[i+3]]<=x?(le[i+3]=1,num=-~num):(le[i+3]=0);
	}
	num/=2;
	for(register int i=1; i<=bcc_cnt; i+=4) {
		dis[i]=dis[i+1]=dis[i+2]=dis[i+3]=0;
	}
	dfs(1,0);
	int st=0,maxx=0;
	for(register int i=1; i<=bcc_cnt; i+=4) {
		maxx<dis[i]&&(maxx=dis[i],st=i);
		maxx<dis[i+1]&&(maxx=dis[i+1],st=i+1);
		maxx<dis[i+2]&&(maxx=dis[i+2],st=i+2);
		maxx<dis[i+3]&&(maxx=dis[i+3],st=i+3);
	}
	for(register int i=1; i<=bcc_cnt; i+=4) {
		dis[i]=dis[i+1]=dis[i+2]=dis[i+3]=0;
	}
	dfs(st,0);
	maxx=0;
	for(register int i=1; i<=bcc_cnt; i+=4) {
		dis[i]>maxx&&(maxx=dis[i]);
		dis[i+1]>maxx&&(maxx=dis[i+1]);
		dis[i+2]>maxx&&(maxx=dis[i+2]);
		dis[i+3]>maxx&&(maxx=dis[i+3]);
	}
	return maxx==num;
}
int main() {
	io.read(n);
	io.read(m);
	int mt=0,minn=N;
	for(register int i=1; i<=m; i++) {
		int a,b,t;
		io.read(a);
		io.read(b);
		io.read(t);
		t<minn&&(minn=t);
		t>mt&&(mt=t);
		add(a,b);
		B[cnt]=t;
		add(b,a);
		B[cnt]=t;
	}
	int num=0;
	dfn[n+1]=dfn[n+2]=dfn[n+3]=1;
	for(register int i=1; i<=n; i+=4) {
		!dfn[i]&&(tj(i,0),num=-~num);
		!dfn[i+1]&&(tj(i+1,0),num=-~num);
		!dfn[i+2]&&(tj(i+2,0),num=-~num);
		!dfn[i+3]&&(tj(i+3,0),num=-~num);
	}
	if(num>2) {
		puts("0");
		return 0;
	}
	if(num==2) {
		printf("%d",minn);
		return 0;
	}
	for(register int i=1; i<=n; i+=4) {
		for(register int j=h[i]; j; j=ne[j]) {
			int a=id[i],b=id[en[j]];
			a<b&&(add_(a,b),key[cnt_]=j,add_(b,a),key[cnt_]=j);
		}
		for(register int j=h[i+1]; j; j=ne[j]) {
			int a=id[i+1],b=id[en[j]];
			a<b&&(add_(a,b),key[cnt_]=j,add_(b,a),key[cnt_]=j);
		}
		for(register int j=h[i+2]; j; j=ne[j]) {
			int a=id[i+2],b=id[en[j]];
			a<b&&(add_(a,b),key[cnt_]=j,add_(b,a),key[cnt_]=j);
		}
		for(register int j=h[i+3]; j; j=ne[j]) {
			int a=id[i+3],b=id[en[j]];
			a<b&&(add_(a,b),key[cnt_]=j,add_(b,a),key[cnt_]=j);
		}
	}
	int l=1,r=mt+1;
	while(l<=r) {
		int mid=l+r>>1;
		bool o=check(mid);
		(o?l:r)=(o?mid=-~mid:mid-1);
	}
	printf("%d",l==mt+2?-1:l);
	return 0;
}