#include <bits/stdc++.h>
using namespace std;
const int N=110,INF=0x3f3f3f3f,M=N*N;
int h[M],to[M],ne[M],tot,w[M];
int d[N],n,k,m,s,t,c[N],a[N][N],ans;
bool st[N];
void add(int x,int y,int z){
	to[++tot]=y;ne[tot]=h[x];w[tot]=z;h[x]=tot;
}
struct node{
	int x,d;
};
struct nn{
	int x,d,t;
};
bool operator <(node aa,node bb){
	return aa.d>bb.d;
}
bool operator <(nn aa,nn bb){
	return aa.t>bb.t;
}
void dist(){
	priority_queue<node> q;
	memset(d,0x3f,sizeof d);
	d[t]=0;q.push((node){t,0});
	while(q.size()){
		int u=q.top().x;q.pop();
		if(st[u])continue;
		st[u]=true;
		for(int i=h[u];i;i=ne[i]){
			int y=to[i];
			if(d[y]>d[u]+w[i]){
				d[y]=d[u]+w[i];
				q.push((node){y,d[y]});
			}
		}
	}
}
bool bfs(){
	priority_queue<nn> q;
	memset(st,false,sizeof st);
	q.push((nn){s,0,0});
	while(q.size()){
		nn u=q.top();q.pop();
		if(st[u.x])continue;
		st[u.x]=true;
		if(u.x==t){
			ans=u.d;return true;
		}
		for(int i=h[u.x];i;i=ne[i]){
			int y=to[i],e=w[i];
			if(a[c[y]][c[u.x]])continue;
			q.push((nn){y,u.d+e,u.d+e+d[y]});
		}
	}
	return false;
} 
int main(){
	cin>>n>>k>>m>>s>>t;
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++)
			scanf("%d",&a[i][j]);
	}
	while(m--){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	dist();
	if(!bfs()){
		cout<<-1;
	}else {
		cout<<ans;
	}
}