题目描述
zy和wd是宿舍里的一对活宝，两个人总是吵架，今天，他们又吵架了。wd威胁要把zy和某个mm的故事传出去。zy需要防止自己的秘密暴露，他要安排对策，但是，他不知道wd把秘密传出去后最少多久全班都会知道。由于lsn是团支书而且熟悉班上每一个人，他给了zy一张表，里面有班里所有的朋友关系，并且对于每对朋友，lsn给出了一个数字表示这对朋友中一个知道zy的秘密后最少多少时间另一个也会知道。不过，对于这么多关系，程序设计只拿了B+的zy实在没有办法了，于是他找到了宿舍里的最后一个成员kk。现在，kk把这个光荣而伟大的任务交给了你，你需要告诉kk在wd传出消息最少多少时间后全班都会知道zy的秘密。
输入
第一行一个整数n表示班级的人数。第二行一个整数m表示lsn提供的关系数。第3至（2+m）行每行三个整数ai,bi,ci，ai、bi表示ai号与bi号同学是一对朋友，ci为这对朋友中一个知道zy的秘密后另一个也知道的最短时间。wd的编号固定为1号。
输出
一行一个整数表示在wd传出消息多少时间后全班都会知道zy的秘密。如果全班中有人永远不会知道zy的秘密，那么则输出让那些能知道zy秘密的人全知道的最短时间。
样例输入
5
6
1 2 3
1 3 4
1 4 5
1 5 6
2 3 1
2 4 4
样例输出
6
数据范围限制
数据范围
0
vard,dis,bz:array[0..100000]of longint;a,b:array[0..2000,0..2000]of longint;n,m,i,j,k,x,y,ans,f,v:longint;
function max(x,y:longint):longint;
beginif x>y then exit(x);exit(y);
end;
procedure spfa(x:longint);
varl,r,p:longint;
beginfillchar(dis,sizeof(dis),$7f);f:=dis[1];l:=0;r:=1;dis[x]:=0; d[1]:=x; bz[x]:=1;while(l<r)dobegininc(l);v:=d[l];for i:=1 to b[v,0] dobegink:=b[v,i]; p:=dis[v]+a[v,k];if(dis[k]>p)thenbegindis[k]:=p;if bz[k]=0 thenbeginbz[k]:=1;inc(r);d[r]:=k;end;end;end;bz[v]:=0;end;
end;
beginassign(input,'secret.in'); reset(input);assign(output,'secret.out'); rewrite(output);readln(n);readln(m);for i:=1 to m dobeginreadln(x,y,v);a[x,y]:=v;a[y,x]:=v;inc(b[x,0]);b[x,b[x,0]]:=y;inc(b[y,0]);b[y,b[y,0]]:=x;end;spfa(1);ans:=-maxlongint;for i:=1 to n doif(dis[i]<>f)thenans:=max(ans,dis[i]);writeln(ans);close(input); close(output);
end.