求条必关

#include <bits/stdc++.h>
using namespace std;
const int N=20010;
const int M=100010;
int n,m,col[N];
struct gragh{
	int tot,hd[N],nxt[M<<1],to[M<<1];
	void add(int a,int b){
		tot++;
		nxt[tot]=hd[a];
		hd[a]=tot;
		to[tot]=b;
	}
}g;
struct edge{
    int a,b,c;
}edges[M];
bool cmp(edge a,edge b){
	return a.c<b.c;
}
bool dfs(int u,int fa,int color){
	col[u]=color;
	for(int i=g.hd[u];i;i=g.nxt[i]){
		int v=g.to[i];
		//cout<<u<<" "<<v<<endl;
		if(v==fa)continue;
		if(col[v]==color){
			return 0;
		}
		if(col[v]==0&&!dfs(v,u,3-color)){
			return 0;
		}
	}
	return 1;
}
bool check(int p){
	g.tot=0;
	memset(g.hd,0,sizeof(g.hd));
	memset(g.nxt,0,sizeof(g.nxt));
	memset(g.to,0,sizeof(g.to));
	memset(col,0,sizeof(col));
	for(int i=p+1;i<=m;i++){
		g.add(edges[i].a,edges[i].b);
		g.add(edges[i].b,edges[i].b);
	}
	for(int i=1;i<=n;i++){
		if(col[i]==0){
			col[i]=1;
			if(!dfs(i,0,1)){
				return 0;
			}
		}
	}
	return 1;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>edges[i].a>>edges[i].b>>edges[i].c;
	}
	sort(edges+1,edges+m+1,cmp);
	int l=1,r=m,mid;
	while(l<r){
		mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid+1;
		cout<<l<<" "<<r<<endl;
	}
	if(m==1)cout<<0<<endl;
	else cout<<edges[l].c<<endl;
	return 0;
}