program cost;
var a:array[1..3000,1..3000]of int64;
    b:array[1..3000]of integer;
    c:array[1..3000]of int64;
    t,k,m,n,i,j,x,y:longint;
    v,min:int64;
procedure sou(i,s,v:int64);
var t,k,j:longint;
begin
if i=y then
  begin
    if s<min then min:=s;
    exit;
  end;
for t:=1 to n do
  if b[t]=0 then
    if (a[i,t]>0)and(a[i,t]<=v) then
      begin
        b[t]:=1;
        if c[t]>s then
          sou(t,c[t],v-a[i,t])
        else sou(t,s,v-a[i,t]);
        b[t]:=0;
      end;
end;
begin
assign(input,'cost.in');
reset(input);
assign(output,'cost.out');
rewrite(output);
readln(n,m,x,y,v);
if n>3000 then
  begin
    writeln(-1);
    close(output);
  end;
for t:=1 to n do
  readln(c[t]);
for t:=1 to m do
  begin
    readln(i,j,k);
    if (a[i,j]=0)or(a[i,j]>k) then
      begin
        a[i,j]:=k;
        a[j,i]:=k;
      end;
  end;
b[x]:=1;
min:=maxlongint;
for t:=1 to n do
  if (a[x,t]>0)and(a[x,t]<=v) then
    begin
      b[t]:=1;
      sou(t,c[t],v-a[x,t]);
      b[t]:=0;
    end;
if min=maxlongint then writeln(-1)
else writeln(min);
close(output);
end.