记录编号	33430	评测结果	AAAAAAWAWA
题目名称	城市	最终得分	80
用户昵称	reamb	是否通过	未通过
代码语言	Pascal	运行时间	0.168 s
提交时间	2011-11-10 16:50:25	内存使用	1.46 MiB

program cost;
var
  final,a,b:array[1..10000]of longint;
  dist:array[1..10000]of int64;
  s:int64;
  right,data,last:array[0..100000]of longint;
  bz:array[1..10000]of boolean;
  n,m,i,ans,u,vv,ss,x,y,z: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 build(x,y,z:longint);
begin
  inc(ss);
  data[ss]:=z;
  right[ss]:=y;
  last[ss]:=final[x];
  final[x]:=ss
end;
procedure spfa(v:longint);
var
  i,t,w,p,d:longint;
  team:array[1..10000]of longint;
begin
  for i:=1 to n do
  begin
    bz[i]:=true;
    dist[i]:=maxlongint
  end;
  if b[u]>v then
    exit;
  dist[u]:=0;
  bz[u]:=false;
  t:=1;
  w:=1;
  team[1]:=u;
  while t<=w do
  begin
    d:=team[t];
    bz[d]:=true;
    inc(t);
    i:=final[d];
    p:=right[i];
    while i<>0 do
    begin
      if (b[p]<=v)and(dist[d]+data[i]<dist[p]) then
      begin
        dist[p]:=dist[d]+data[i];
        if bz[p] then
        begin
          inc(w);
          team[w]:=p;
          bz[p]:=false
        end
      end;
      i:=last[i];
      p:=right[i]
    end
  end
end;
procedure find(x,y:longint);
var
  mid:longint;
begin
  mid:=(x+y)div 2;
  if x=y then
  begin
    ans:=a[x];
    exit
  end
  else
  begin
    spfa(a[mid]);
    if dist[vv]<=s then
      find(x,mid)
    else
      find(mid+1,y)
  end;
end;
begin
  assign (input,'cost.in');
  reset (input);
  assign (output,'cost.out');
  rewrite (output);
    readln (n,m,u,vv,s);
    for i:=1 to n do
    begin
      readln (a[i]);
      b[i]:=a[i];
    end;
    sort(1,n);
    for i:=1 to m do
    begin
      readln (x,y,z);
      build(x,y,z);
      build(y,x,z)
    end;
    spfa(maxlongint);
    if (dist[vv]=maxlongint)or(dist[vv]>s) then
    begin
      writeln ('-1')
    end
    else
    begin
      find(1,n);
      writeln (ans)
    end;
  close (input);
  close (output)
end.