记录编号	33471	评测结果	AAAAAAAAWA
题目名称	城市	最终得分	90
用户昵称	Des.	是否通过	未通过
代码语言	Pascal	运行时间	1.311 s
提交时间	2011-11-10 19:33:13	内存使用	7.31 MiB

program cost;
var a:array[1..10002,1..2]of longint;
    b,next,v:array[1..100002]of int64;
    c:array[1..10001]of int64;
    d:array[1..10001]of int64;
    bo:array[1..10002]of boolean;
    q:array[1..600002]of int64;
    t:longint;
    k,m,n,i,j,st,en,tot:int64;
    s:int64;
    f:array[1..10002]of int64;
    can:array[1..10002]of boolean;
procedure qsort(l,r:longint);
var i,j,k:longint;
    a,m:int64;
begin
k:=(l+r)div 2;
m:=c[k];
i:=l;
j:=r;
repeat
  while c[i]<m do inc(i);
  while c[j]>m do dec(j);
  if i<=j then
    begin
      a:=c[i];
      c[i]:=c[j];
      c[j]:=a;
      a:=d[i];
      d[i]:=d[j];
      d[j]:=a;
      inc(i);
      dec(j);
    end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;


function spfa(p:longint):boolean;
var t,k,i,j:longint;
begin
for t:=1 to n do
  f[t]:=maxlongint*100000;
fillchar(can,sizeof(can),true);
for t:=p+1 to n do
  can[d[t]]:=false;
if can[st]=false then exit(false);
if can[en]=false then exit(false);
f[st]:=0;
i:=0;
j:=1;
q[1]:=st;
fillchar(bo,sizeof(bo),true);
bo[st]:=false;
repeat
  inc(i);
  k:=q[i];
  t:=a[k,1];
  repeat
    if can[b[t]] then
      if f[k]+v[t]<f[b[t]] then
        begin
          f[b[t]]:=f[k]+v[t];
          if bo[b[t]] then
            begin
              inc(j);
              q[j]:=b[t];
              bo[b[t]]:=false;
            end;
        end;
    t:=next[t];
  until t=0;
  bo[k]:=true;
until i=j;
if f[en]<=s then exit(true)
else exit(false);
end;


function find(l,r:longint):longint;
var t,k,j:longint;
begin
if l=r then exit(l);
k:=(l+r)div 2;
if spfa(k) then exit(find(l,k))
else exit(find(k+1,r));
end;
begin
assign(input,'cost.in');
reset(input);
assign(output,'cost.out');
rewrite(output);
readln(n,m,st,en,s);
for t:=1 to n do
  readln(c[t]);
for t:=1 to m do
  begin
    readln(i,j,k);
    if a[i,1]=0 then
      begin
        inc(tot);
        a[i,1]:=tot;
        a[i,2]:=tot;
        b[tot]:=j;
        v[tot]:=k;
      end
    else
      begin
        inc(tot);
        next[a[i,2]]:=tot;
        a[i,2]:=tot;
        b[tot]:=j;
        v[tot]:=k;
      end;
    if a[j,1]=0 then
      begin
        inc(tot);
        a[j,1]:=tot;
        a[j,2]:=tot;
        b[tot]:=i;
        v[tot]:=k;
      end
    else
      begin
        inc(tot);
        next[a[j,2]]:=tot;
        a[j,2]:=tot;
        b[tot]:=i;
        v[tot]:=k;
      end;
  end;
for t:=1 to n+1 do
  d[t]:=t;
qsort(1,n);
c[n+1]:=-1;
k:=find(1,n+1);
writeln(c[k]);
close(output);
end.