https://www.luogu.com.cn/record/200685526

using namespace std;

int n,m;

struct Node
{
	int a,b,c;
};

Node conf[1000005];

bool cmd(Node i,Node j)
{
	return i.c>j.c;
}

vector<int> dir[200005];

int l[200005];

bool dfs(int u,int col)
{
	l[u]=col;
	for(int i=0;i<dir[u].size();i++)
	{
		if(l[dir[u][i]]!=0 and l[u]==l[dir[u][i]])
			return 0;
		else if(l[dir[u][i]]==0 and dfs(dir[u][i],(col%2)+1)==0)
			return 0;
	}
	return 1;
}

bool check(int num)
{
	if(conf[1].c<=num)
		return 1;
	for(int i=1;i<=n;i++)
		while(dir[i].size())
			dir[i].pop_back();
	for(int i=1;conf[i].c>num;i++)
	{
		dir[conf[i].a].push_back(conf[i].b);
		dir[conf[i].b].push_back(conf[i].a);
	}
	memset(l,0,sizeof(l));
	return dfs(conf[1].a,1);
}

int main()
{
	scanf("%d",&n);
	scanf("%d",&m);
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&conf[i].a);
		scanf("%d",&conf[i].b);
		scanf("%d",&conf[i].c);
	}
	
	sort(conf+1,conf+1+m,cmd);
	
	int left,right,mid,ans;
	left=0;
	right=1000000005;
	while(left<=right)
	{
		mid=(left+right)/2;
		if(check(mid))
		{
			right=mid-1;
			ans=mid;
		}
		else
		{
			left=mid+1;
		}
	}
	cout<<ans;
	return 0;
}```