二分+2-SAT
先预处理出所有的v，然后离散化一下，在那个的基础上二分，对于每次二分出的值约束边权超过所二分出的边权的两点。
//OJ 1322
//by Cydiater
//2015.8.26
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <ctime>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <cmath>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
map<int,int>m;
,cnt=,num[MAXN],leftt,rightt,len=,group[MAXN],group_num,dfn[MAXN],low[MAXN],stack[MAXN],node[MAXN][],part=,dfs_clock=;
bool vis[MAXN];
struct edge{
int y,next,x;
}e[MAXN];
struct Prison{
int x,y,v;
}a[MAXN];
namespace solution{
inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].x=x;}
void init(){
N=read();M=read();
tmp[++top]=;
up(i,,M){
a[i].x=read();a[i].y=read();a[i].v=read();
tmp[++top]=a[i].v;
}
sort(tmp+,tmp+top+);
up(i,,top)if(!m[tmp[i]]){
m[tmp[i]]=++cnt;
num[cnt]=tmp[i];
}
up(i,,N)up(j,,)node[i][j]=++part;
}
void tarjan(int node){
dfn[node]=low[node]=++dfs_clock;
vis[node]=;stack[++top]=node;
for(int i=LINK[node];i;i=e[i].next)
if(!dfn[e[i].y]){
tarjan(e[i].y);
low[node]=min(low[node],low[e[i].y]);
}else if(vis[e[i].y]) low[node]=min(low[node],dfn[e[i].y]);
if(low[node]==dfn[node]){
int tmp;group_num++;
do{
tmp=stack[top--];
vis[tmp]=;
group[tmp]=group_num;
}while(tmp!=node);
}
}
bool check(int xx){
len=;top=;dfs_clock=;group_num=;
memset(LINK,,sizeof(LINK));
memset(dfn,,sizeof(dfn));
memset(vis,,sizeof(vis));
up(i,,M)if(a[i].v>xx){
int x=a[i].x,y=a[i].y;
//cout<<x<<' '<<y<<endl;
insert(node[x][],node[y][]);
insert(node[y][],node[x][]);
insert(node[x][],node[y][]);
insert(node[y][],node[x][]);
}
up(i,,N<<)if(!dfn[i])tarjan(i);
up(i,,N)]]==group[node[i][]]);
;
}
void slove(){
leftt=;rightt=cnt;
<rightt){
;
if(check(num[mid])) rightt=mid;
else leftt=mid;
}
}
void output(){
if(check(num[leftt])){
cout<<num[leftt]<<endl;
}else
cout<<num[rightt]<<endl;
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
output();
;
}