思路如下:

首先染色法判断是否为二分图，如果不是，断权最小边，即放任这个最小冲突发生，然后再染色法判断，断边，直至是二分图

#include<bits/stdc++.h>
#include<queue>
using namespace std;

#define N 20005
#define M 1000005

struct node
{
	int v,w,prev,next,h;
};

int n,m,head[N],idx,color[N],ans=0,pd[N];
node edge[M];

void add(int x,int y,int w)
{
	edge[++idx].v=y;
	edge[idx].w=w;
	edge[idx].prev=0;
	edge[idx].next=head[x];
	edge[head[x]].prev=idx;
	edge[idx].h=x;
	head[x]=idx;
}

void pop(int i)
{
	edge[edge[i].prev].next=edge[i].next;
	edge[edge[i].next].prev=edge[i].prev;
	if(edge[i].prev==0)head[edge[i].h]=edge[i].next;
	edge[i].w=INT_MAX;
	i=edge[i].v;
	edge[edge[i].prev].next=edge[i].next;
	edge[edge[i].next].prev=edge[i].prev;
	if(edge[i].prev==0)head[edge[i].h]=edge[i].next;
	edge[i].w=INT_MAX;
}

bool checkf(int i,int colors)
{
	queue<int>Q;
	Q.push(i);
	while(!Q.empty())
	{
		for(int jt=head[Q.front()];jt!=0;jt=edge[jt].next)
		{
			int j=edge[jt].v;
			if(color[j]&&color[j]==color[Q.front()])return false;
			if(!color[j])Q.push(j);
			color[j]=3-color[Q.front()];
		}
		Q.pop();
	}
	return true;
}

bool check()
{
	for(int i=1;i<=n;++i)
	{
		memset(color,0,sizeof(color));
		if(!checkf(i,1))return false;
	}
	return true;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
    	int x,y,w;
    	scanf("%d%d%d",&x,&y,&w);
    	add(x,y,w);
    	add(y,x,w);
	}
	while(!check())
	{
		int mini=1;
		for(int i=1;i<=idx;++i)if(edge[mini].w>edge[i].w)mini=i;
		ans=edge[mini].w;
		pop(mini);
	}
	printf("%d",ans);
	return 0;
}

20pts