1 //OJ 1322  2 //by Cydiater  3 //2015.8.26  4 #include <iostream>  5 #include <cstdio>  6 #include <cstring>  7 #include <queue>  8 #include <map>  9 #include <ctime> 10 #include <string> 11 #include <algorithm> 12 #include <iomanip> 13 #include <cstdlib> 14 #include <cmath> 15 using namespace std; 16 #define ll long long 17 #define up(i,j,n)       for(int i=j;i<=n;i++) 18 #define down(i,j,n)     for(int i=j;i>=n;i--) 19 const int MAXN=1e6+5; 20 const int oo=0x3f3f3f3f; 21 inline int read(){ 22       char ch=getchar();int x=0,f=1; 23       while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 24       while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 25       return x*f; 26 } 27 map<int,int>m; 28 int N,LINK[MAXN],M,tmp[MAXN],top=0,cnt=0,num[MAXN],leftt,rightt,len=0,group[MAXN],group_num,dfn[MAXN],low[MAXN],stack[MAXN],node[MAXN][2],part=0,dfs_clock=0; 29 bool vis[MAXN]; 30 struct edge{ 31       int y,next,x; 32 }e[MAXN]; 33 struct Prison{ 34       int x,y,v; 35 }a[MAXN]; 36 namespace solution{ 37       inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].x=x;} 38       void init(){ 39             N=read();M=read(); 40             tmp[++top]=0; 41             up(i,1,M){ 42                   a[i].x=read();a[i].y=read();a[i].v=read(); 43                   tmp[++top]=a[i].v; 44             } 45             sort(tmp+1,tmp+top+1); 46             up(i,1,top)if(!m[tmp[i]]){ 47                   m[tmp[i]]=++cnt; 48                   num[cnt]=tmp[i]; 49             } 50             up(i,1,N)up(j,0,1)node[i][j]=++part; 51       } 52       void tarjan(int node){ 53             dfn[node]=low[node]=++dfs_clock; 54             vis[node]=1;stack[++top]=node; 55             for(int i=LINK[node];i;i=e[i].next) 56                   if(!dfn[e[i].y]){ 57                         tarjan(e[i].y); 58                         low[node]=min(low[node],low[e[i].y]); 59                   }else if(vis[e[i].y]) low[node]=min(low[node],dfn[e[i].y]); 60             if(low[node]==dfn[node]){ 61                   int tmp;group_num++; 62                   do{ 63                         tmp=stack[top--]; 64                         vis[tmp]=0; 65                         group[tmp]=group_num; 66                   }while(tmp!=node); 67             } 68       } 69       bool check(int xx){ 70             len=0;top=0;dfs_clock=0;group_num=0; 71             memset(LINK,0,sizeof(LINK)); 72             memset(dfn,0,sizeof(dfn)); 73             memset(vis,0,sizeof(vis)); 74             up(i,1,M)if(a[i].v>xx){ 75                   int x=a[i].x,y=a[i].y; 76                   //cout<<x<<‘ ‘<<y<<endl; 77                   insert(node[x][0],node[y][1]); 78                   insert(node[y][1],node[x][0]); 79                   insert(node[x][1],node[y][0]); 80                   insert(node[y][0],node[x][1]); 81             } 82             up(i,1,N<<1)if(!dfn[i])tarjan(i); 83             up(i,1,N)if(group[node[i][1]]==group[node[i][0]])return 0; 84             return 1; 85       } 86       void slove(){ 87             leftt=1;rightt=cnt; 88             while(leftt+1<rightt){ 89                   int mid=(leftt+rightt)>>1; 90                   if(check(num[mid]))     rightt=mid; 91                   else                    leftt=mid; 92             } 93       } 94       void output(){ 95             if(check(num[leftt])){ 96                   cout<<num[leftt]<<endl; 97             }else 98                   cout<<num[rightt]<<endl; 99       }100 }101 int main(){102       //freopen("input.in","r",stdin);103       using namespace solution;104       init();105       slove();106       output();107       return 0;108 }