传送门啦

想让最大值最小，所以，这题可以用二分法，排序之后发现可以并查集，因为要使最大值最小，排序后这个最大值是存在的。

对于会冲突的两个罪犯，我们连一条无向边，然后按权值从大到小排序，从大到小枚举每一条边，如果边上的两个罪犯已经在一个*，那么输出结果。

冤家路窄没办法咯

否则将两个罪犯放到不同的*，我们考虑用并查集实现。

如果a和b不在一个*，b和c不在一个*，那么a和c一定在一个*（题目中说明只有两个*）。

我们将并查集的大小扩大一倍，来建立罪犯的补集，即不在同一个*的罪犯的集合.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxm = 100000,maxn = 20000;

int n,m;

struct Edge{

	int a;

	int b;

	int w;

}e[maxm];

int f[maxn * 2];

bool cmp(Edge x,Edge y){

    return x.w > y.w;

}

int find(int x){

	if(f[x] != x)  f[x] = find(f[x]);

	return f[x];

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i = 1; i <= m; i++)

       scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);

    for(int i = 1; i <= n * 2; i++)

       f[i] = i;

    sort(e + 1,e + m + 1,cmp);

    for(int i = 1; i <= m; i++){

        int x = find(e[i].a) , y = find(e[i].b);

        if(x == y){

            printf("%d\n", e[i].w);

            return 0;

        }

        int xx = find(e[i].a + n) , yy = find(e[i].b + n);

        f[x] = yy;

        f[y] = xx;

    }

    printf("0\n");

    return 0;

}