记录编号	21957	评测结果	AAAAAEEEEA
题目名称	城市	最终得分	60
用户昵称	苏轼	是否通过	未通过
代码语言	Pascal	运行时间	0.602 s
提交时间	2010-11-16 12:13:52	内存使用	124.49 MiB

program cost(input,output);

type
  re=record
    en,next:longint;
    l:int64;
  end;

const
  maxlonglongint=10000000000;

var
  n,m,u,v,a,b,c,tl,s:int64;
  i:longint;
  f,tail:array[1..50000]of longint;
  way:array[1..80000]of re;
  ik:array[0..80000,0..200]of int64;
  boo:array[1..100000]of boolean;

procedure add_way(const a,b:longint; const c:int64);
  begin
    if tail[a]=0 then
    begin
      tail[a]:=a;
      way[a].en:=b;
      way[a].l:=c;
    end
    else
    begin
      inc(tl);
      way[tl].en:=b;
      way[tl].l:=c;
      way[tail[a]].next:=tl;
      tail[a]:=tl;
    end;
  end;

function go(const city:longint; const oil:int64):int64;
  var
    i:longint;
    tmp,mi:int64;
  begin
    if ik[city,oil]<>0 then
      exit(ik[city,oil]);

    if oil<0 then
      exit(maxlonglongint);

    if city<>v then
    begin
      i:=city;
      mi:=maxlonglongint;
      while i<>0 do
      begin
        if not boo[way[i].en] then
        begin
          boo[way[i].en]:=true;
          tmp:=go(way[i].en,oil-way[i].l);
          boo[way[i].en]:=false;

          if tmp<mi then
            mi:=tmp;
        end;
        i:=way[i].next;
      end;

      if mi>f[city] then
        ik[city,oil]:=mi
      else
        ik[city,oil]:=f[city];
    end
    else
      ik[city,oil]:=f[city];

    exit(ik[city,oil]);
  end;

begin
  assign(input,'cost.in');
  reset(input);
  assign(output,'cost.out');
  rewrite(output);

  readln(n,m,u,v,s);
  for i:=1 to n do
    readln(f[i]);

  tl:=n;
  for i:=1 to m do
  begin
    readln(a,b,c);
    add_way(a,b,c);
    add_way(b,a,c);
  end;

  boo[u]:=true;
  a:=go(u,s);
  if a>maxlonglongint div 10 then
    a:=-1;
  writeln(a);

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