记录编号	20311	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Jan08] 架设电话线	最终得分	100
用户昵称	reamb	是否通过	通过
代码语言	Pascal	运行时间	0.984 s
提交时间	2010-10-23 14:15:12	内存使用	7.79 MiB

program jiashedianhuaxian;
var
  ma,map:array[1..1000,1..1000]of longint;
  a:array[1..10000]of longint;
  q,dist:array[1..1000]of longint;
  biaozhi:array[1..1000]of boolean;
  i,j,n,p,k,x,y,l,s,t,w:longint;
procedure sort(l,r: longint);
var
  i,j,x,y: longint;
begin
  i:=l;
  j:=r;
  x:=a[(l+r) div 2];
  repeat
    while a[i]<x do
      inc(i);
    while x<a[j] do
      dec(j);
    if not(i>j) then
    begin
      y:=a[i];
      a[i]:=a[j];
      a[j]:=y;
      inc(i);
      j:=j-1;
    end;
  until i>j;
  if l<j then
    sort(l,j);
  if i<r then
    sort(i,r);
end;
procedure spfa;
begin
  fillchar(q,sizeof(q),0);
  fillchar(biaozhi,sizeof(biaozhi),true);
  for i:=1 to n do
    dist[i]:=maxlongint;
  t:=0;
  w:=1;
  q[1]:=1;
  biaozhi[1]:=false;
  dist[1]:=0;
  while t<>w do
  begin
    t:=(t mod n)+1;
    s:=q[t];
    biaozhi[s]:=true;
    for i:=1 to n do
      if (ma[s,i]<>maxlongint)and(dist[s]+ma[s,i]<dist[i]) then
      begin
        dist[i]:=dist[s]+ma[s,i];
        if biaozhi[i] then
        begin
          w:=(w mod n)+1;
          q[w]:=i;
          biaozhi[i]:=false
        end
      end
  end
end;
procedure ans(x,y:longint);
begin
  if x=y then
  begin
    writeln (a[x]);
    close (input);
    close (output);
    halt
  end;
  s:=a[(x+y)div 2];
  for i:=1 to n do
    for j:=1 to n do
      if map[i,j]>s then
        ma[i,j]:=1
      else
        if map[i,j]=0 then
          ma[i,j]:=maxlongint
        else
          ma[i,j]:=0;
  spfa;
  if dist[n]>k then
    ans((x+y)div 2+1,y)
  else
    ans(x,(x+y)div 2)
end;
begin
  assign (input,'phoneline.in');
  reset (input);
  assign (output,'phoneline.out');
  rewrite (output);
    readln (n,p,k);
    for i:=1 to n do
      for j:=1 to n do
        ma[i,j]:=maxlongint;
    for i:=1 to p do
    begin
      readln (x,y,l);
      a[i]:=l;
      map[x,y]:=l;
      map[y,x]:=l;
      ma[x,y]:=1;
      ma[y,x]:=1
    end;
    spfa;
    if dist[n]<=k then
    begin
      writeln ('0');
      close (input);
      close (output);
      halt
    end;
    if dist[n]=maxlongint then
    begin
      writeln ('-1');
      close (input);
      close (output);
      halt
    end;
    sort(1,p);
    ans(1,p);
  close (input);
  close (output)
end.