没必要二分，因为M的规模只有1e6，直接贪心从大到小判断是否冲突，冲突就结束并输出。
扩展域和带权并查集都可以实现关系的传递，下面提供一个带权并查集的做法，带权并查集就是find函数区别与普通并查集。

C++ 代码

// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define xx first
#define yy second
#define ls x * 2
#define rs x * 2 + 1
// #define int long long
using namespace std;
using ll = long long;
using ld = long double;
using PII = pair<int, int>;
const int N = 1e5+7;
const int INF = 0x3f3f3f3f;
const int eps = 1e-8;
const int mod = 1e9+7;

int d[N], n, m, fa[N];

int find(int x){
    if (fa[x] == x) return x;
    int p = find(fa[x]);
    d[x] ^= d[fa[x]];
    return fa[x] = p;
}

struct Node{
    int a, b, c;
    bool operator <(const Node &y) const{
        return this->c > y.c;
    }
}a[N];

void solve()
{ 
    cin >> n >> m;
    for (int i = 1; i <= m; i ++){
        cin >> a[i].a >> a[i].b >> a[i].c;
    }
    sort(a + 1, a + 1 + m);
    for (int i = 1; i <= n; i ++) fa[i] = i;
    for (int i = 1; i <= m; i ++){
        int x = a[i].a, y = a[i].b;
        int fx = find(x), fy = find(y);
        if (fx != fy){
            fa[fx] = fy;
            d[fx] = d[x] ^ d[y] ^ 1;
        }
        else if (d[x] ^ d[y] == 0){
            cout << a[i].c << '\n';
            return;
        }
    }
    cout << "0\n";
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cout.tie(0);
    int tt = 1;
    // cin >> tt;
    while(tt --) solve();
    return 0;
}