记录编号	15448	评测结果	AAAAAAAAAA
题目名称	电话网络	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	2.389 s
提交时间	2009-11-13 09:18:08	内存使用	3.92 MiB

program DianHuaWangLuo;
var
  a:array[1..1000,1..1000] of longint;
  n,m,k,i,j,ans,r1,r2,l,r,r3:longint;
procedure djs(p:longint);
var
  a1:array[1..1000,1..1000] of integer;
  arrive:array[1..1000] of boolean;
  cost:array[1..1000] of integer;
  i,j,min,mini,t:integer;
begin
  for i:=1 to n do
  begin
    for j:=1 to n do
      if a[i,j]>0 then
      begin
        if a[i,j]<=p
          then a1[i,j]:=0
          else a1[i,j]:=1
      end
      else
        a1[i,j]:=32767;
    cost[i]:=32767
  end;
  cost[1]:=0;
  fillchar(arrive,sizeof(arrive),false);
  arrive[1]:=true;
  t:=1;
  repeat
    for i:=1 to n do
    begin
      if a1[t,i]<32767 then
      begin
        if (cost[t]+a1[t,i]<cost[i]) and (arrive[i]=false) then
        begin
          cost[i]:=cost[t]+a1[t,i];
        end
      end
    end;
    min:=32767;
    for i:=1 to n do
      if (arrive[i]=false) and (min>cost[i]) then
      begin
        min:=cost[i];
        mini:=i
      end;
    if min<32767 then
    begin
      arrive[mini]:=true;
      t:=mini;
    end
  until (t=n) or (min=32767);
  ans:=cost[n]
end;

begin
  assign(input,'phone.in');
  reset(input);
  assign(output,'phone.out');
  rewrite(output);
  readln(n,m,k);
  fillchar(a,sizeof(a),0);

  l:=0;
  r:=0;
  for i:=1 to m do
  begin
    readln(r1,r2,r3);
    a[r1,r2]:=r3;
    a[r2,r1]:=r3;
    if r3>r
      then r:=r3
  end;

  repeat
    djs((l+r) div 2);
    if ans<=k
      then r:=(l+r) div 2
      else l:=(l+r) div 2+1;
    if ans>1000 then
    begin
      l:=-1;
      break
    end;
  until l>=r;

  writeln(l);
  close(input);
  close(output)
end.