program noip2010_3; //关押罪犯type edg=record x,ti,cost,next:longint; end;var n,m,a,b,c,ans,mid,i,tot,L,r:longint; flag:boolean; edge,edget:array[1..100000] of edg; head,color:array[1..100000] of longint;procedure sort(L,r:longint);var i,j:longint; temp:edg;begin i:=L;j:=r;temp:=edget[L]; while i<j do begin while (i<j)and(temp.cost<=edget[j].cost) do dec(j); edget[i]:=edget[j]; while (i<j)and(temp.cost>=edget[i].cost) do inc(i); edget[j]:=edget[i]; end; edget[i]:=temp; if i+1<r then sort(i+1,r); if i-1>L then sort(L,i-1);end;
procedure add(a,b,c:longint);begin edge[tot].ti:=b; edge[tot].cost:=c; edge[tot].next:=head[a]; head[a]:=tot; inc(tot);end;
procedure check(x:longint);var j,y:longint;begin j:=head[x]; while j<>-1 do begin y:=edge[j].ti; if color[y]=-1 then begin color[y]:=1-color[x]; check(y); end else if color[y]=color[x] then flag:=false; j:=edge[j].next; end;end;
begin readln(n,m); for i:=1 to m do begin readln(a,b,c); edget[i].x:=a; edget[i].ti:=b; edget[i].cost:=c; end; sort(1,m); for i:=1 to m do begin writeln(edget[i].cost); end; L:=1; r:=m; ans:=0; while L<=r do begin mid:=(L+r) div 2; flag:=true; for i:=1 to n do head[i]:=-1; tot:=0; for i:=mid to m do begin add(edget[i].x,edget[i].ti,edget[i].cost); add(edget[i].ti,edget[i].x,edget[i].cost); end; for i:=1 to n do if color[i]=-1 then begin color[i]:=1; check(i); end; if not flag then begin L:=mid+1; ans:=edget[mid].cost; end else r:=mid-1; end; writeln(ans); readln;end.
procedure add(a,b,c:longint);begin edge[tot].ti:=b; edge[tot].cost:=c; edge[tot].next:=head[a]; head[a]:=tot; inc(tot);end;
procedure check(x:longint);var j,y:longint;begin j:=head[x]; while j<>-1 do begin y:=edge[j].ti; if color[y]=-1 then begin color[y]:=1-color[x]; check(y); end else if color[y]=color[x] then flag:=false; j:=edge[j].next; end;end;
begin readln(n,m); for i:=1 to m do begin readln(a,b,c); edget[i].x:=a; edget[i].ti:=b; edget[i].cost:=c; end; sort(1,m); for i:=1 to m do begin writeln(edget[i].cost); end; L:=1; r:=m; ans:=0; while L<=r do begin mid:=(L+r) div 2; flag:=true; for i:=1 to n do head[i]:=-1; tot:=0; for i:=mid to m do begin add(edget[i].x,edget[i].ti,edget[i].cost); add(edget[i].ti,edget[i].x,edget[i].cost); end; for i:=1 to n do if color[i]=-1 then begin color[i]:=1; check(i); end; if not flag then begin L:=mid+1; ans:=edget[mid].cost; end else r:=mid-1; end; writeln(ans); readln;end.
