链式前向星+深搜
#include <iostream>
#include <vector>
using namespace std;
const int inf = 1e9+7;
const int MAXN = 20005;
const int MAXM = 100005;
struct edges
{
int to;
int nx;
int val;
}a[MAXM*2];
int head[MAXN];
int tot = 0;
//vector<int> gra[MAXM];
int color[MAXN];
void add(int x,int y,int val)
{
a[tot].to = y;
a[tot].val = val;
a[tot].nx = head[x];
head[x] = tot++;
}
void ini()
{
for(int i=0;i<MAXN;i++)
head[i] = -1,color[i] = -1;
}
bool ok;
void dfs(int now,int col,int mid)
{
color[now] = col;
for(int i=head[now];~i;i = a[i].nx)
{
int y = a[i].to;
if(a[i].val <= mid)
continue;
if(color[now] == color[y])
{
ok = false;
return ;
}
if(color[y] == -1)
{
dfs(y,col^1,mid);
if(!ok) return ;
}
}
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
// node all[m];
ini();
for(int i=0;i<m;i++)
{
// scanf("%d %d %d",&all[i].x,&all[i].y,&all[i].val);
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
int le = 0,ri = inf;
while(le < ri)
{
int mid = (le + ri)/2;
// for(int i=0;i<m;i++)
// {
// if(all[i].val > mid)
// {
// gra[all[i].x].push_back(all[i].y);
// gra[all[i].y].push_back(all[i].x);
// }
// }
for(int i=0;i<=n;i++)
color[i] = -1;
ok = true;
for(int i=1;i<=n;i++)
{
if(color[i] == -1)
dfs(i,0,mid);
if(!ok)
break;
}
if(ok)
ri = mid;
else
le = mid+1;
}
cout<<le;
return 0;
}