记录编号	14163	评测结果	AAAAAAAAAA
题目名称	电话网络	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	Pascal	运行时间	1.836 s
提交时间	2009-10-27 16:06:06	内存使用	3.93 MiB

program xmz;
var
f1,f2:text;
i,n,p,k,t1,t2,maxx:longint;
f:array[1..1000,1..1000]of longint;
procedure cha(l,r:longint);
 var
 y:array[1..1000]of boolean;
 d:array[1..1000]of longint;
 mid,c,a,min:longint;
 begin
  mid:=(l+r)div 2;
  c:=1;

  for a:=1 to n do
   begin
   d[a]:=99999999;
   y[a]:=false;
   end;
   d[1]:=0;
  repeat
   y[c]:=true;
   for a:=1 to n do
    begin
    if (f[c,a]<=mid)and(f[c,a]<>0)and(d[a]>d[c]) then
     d[a]:=d[c];
    if (f[c,a]>mid)and(f[c,a]<>0)and(d[a]>d[c]+1) then
     d[a]:=d[c]+1;
    end;
   min:=99999999;
   for a:=1 to n do
    if(d[a]<min)and(not y[a]) then begin min:=d[a];c:=a;end;
  until min=99999999;

   if(d[n]<=k)and(l=r)then write(f2,l);
   if (d[n]>k)and(l=r)then write(f2,-1);

   if l<>r then
   if d[n]<=k then cha(l,mid)
   else cha(mid+1,r);
 end;


begin
 assign(f1,'phone.in');assign(f2,'phone.out');
 reset(f1);rewrite(f2);
  read(f1,n,p,k);
  for i:=1 to p do
   begin
    read(f1,t1,t2);
    read(f1,f[t1,t2]);
    f[t2,t1]:=f[t1,t2];
    if f[t1,t2]>maxx then maxx:=f[t1,t2];
   end;
  cha(0,maxx);
 close(f1);close(f2);
end.