简要题意：
给定若干组关系，第 (i) 组关系形如 “(x) 号罪犯和 (y) 号罪犯有 (z) 的矛盾”。现在共有两个监狱，在同一个监狱即会产生矛盾。问最小矛盾值。
显然，考虑 并查集 维护。
先按 (z) 从大到小排序，考虑一对对检验，不合法退出即可。
本题我们要维护 不等关系，即 (x ot = y) ，不能满足则答案为 (z).
不等关系如何维护？可以考虑一个 (2) 倍空间的方法.
显然，本题中，如果 (a ot = b , b ot = c)，则 (a=c)（(a,b,c) 为某罪犯关押的监狱编号且 (in (0,1))），所以 (2) 倍空间即可。（几个监狱就几倍）
考虑对于每组 (x,y)，本着 敌人的敌人是朋友 的原则，用(f) 表示 和自己一个监狱的集合，那么：
对于每组 (x,y)，用 (f_x = f_y) 或 (f_{x+n} = f_{y+n}) 表示 当且 (x,y) 在同一个监狱。可以理解一下：(f_x = f_y) 是显然，(f_{x+n} = f_{y+n}) 意为，两个人 同时和另一个人不在一个监狱，根据上面 (a,b,c) 的性质，可得两个人也是同一个监狱。
那么如何维护呢？显然，只要将 (x) 和 (y+n) 放在同一个监狱，(y) 和 (x+n) 放在同一个监狱，这样就解决了问题。
那么你问了：这样要枚举整个集合，怎么办？
我会平衡树！我会莫队！我会队列！我会 ( ext{set})！
不得不说，如果你给每个节点开 ( ext{set}) 的话，显然 (O(n^2)) 空间等着你。
所以，可以发现 (f_x) 实际上记得是 和 (x) 同一个监狱的首领，而合并，查询等操作均为 并查集 维护操作。
综上可以通过。
时间复杂度：(O(n log n)).（显然并查集常数 (alpha) 不如排序多出的 (log n) 大，忽略不计）
实际得分：(100pts).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;}
inline void write(int x) {
if(x<0) {putchar('-');write(-x);return;}
if(x<10) {putchar(char(x%10+'0'));return;}
write(x/10);putchar(char(x%10+'0'));
}
struct data {
int x,y,z;
} a[N];
int n,m,f[N];
inline bool cmp(data u,data v) {
return u.z>v.z;
} //排序
inline int find(int x) {return f[x]==x?x:f[x]=find(f[x]);} //查询
int main() {
n=read(),m=read();
for(int i=1;i<=m;i++) a[i].x=read(),a[i].y=read(),a[i].z=read();
sort(a+1,a+1+m,cmp);
int l=1,r=n,ans;
for(int i=1;i<=(n<<1);i++) f[i]=i;
for(int i=1;i<=m+1;i++) { //做到 m+1 是因为如果矛盾值为 0 则 i=m+1 时处理
int x=a[i].x,y=a[i].y,z=a[i].z;
if(find(x)==find(y) || find(x+n)==find(y+n)) {printf("%d
",z);return 0;}
f[f[x+n]]=f[y]; f[f[x]]=f[y+n]; //合并
}
return 0;
}