Var
n,k,m,t,i,j,h,s,u,v,d,t1:longint;
a,state,ws,sq:array[1..10000]of longint;
b,f,wh:array[1..1000,1..1000]of longint;

Function pd(x,y,z:longint):boolean;
Var
i:longint;
Begin
if z=1 then
begin
for i:=1 to ws[x] do
if b[y,wh[x,i]]=1 then
exit(false);
exit(true);
end
else
begin
for i:=1 to ws[x] do
if wh[x,i]=a[y] then
exit(false);
exit(true);
end;
End;

Begin
readln(n,k,m,s,t1);
for i:=1 to n do
read(a[i]);
for i:=1 to k do
begin
for j:=1 to k do
read(b[i,j]);
readln;
end;
for i:=1 to m do
begin
readln(u,v,d);
if f[u,v]=0 then
begin
f[u,v]:=d;
f[v,u]:=d;
end
else
if f[u,v]>d then
begin
f[u,v]:=d;
f[u,v]:=d;
end;
end;
for i:=2 to n do
sq[i]:=30000;
state[1]:=s;
wh[1,1]:=a[s];
ws[1]:=1;
t:=1;
repeat
inc(h);
for i:=1 to n do
if (pd(h,i,1)) and (pd(h,i,2)) and (f[state[h],i]<>0) and (f[state[h],i]+sq[state[h]]<sq[i])
then
begin
inc(t);
state[t]:=i;
sq[i]:=f[state[h],i]+sq[state[h]];
for j:=1 to ws[h] do
wh[t,j]:=wh[h,j];
ws[t]:=ws[h]+1;
wh[t,ws[t]]:=a[i];
if i=t1 then
begin
writeln(sq[t1]);
readln;
exit;
end;
end;
until h>=t;
writeln(-1);
readln;
End.