#include<iostream>
#include<cstdio>
using namespace std;
int head[20005],nex[20005],to[20005],val[20005],n,m,k,s,t,tot,ans=1000000;
int wh[105],a[105][105];bool v[105],vc[105];
void add(int x,int y,int v1){
	to[++tot]=y;
	val[tot]=v1;
	nex[tot]=head[x];
	head[x]=tot;
}
void dfs(int x,int y,int stap){
	if(stap>=ans)return;
	if(x==y){ans=min(ans,stap);return;}
	for(int i=head[x];i;i=nex[i]){
		int go=to[i];
		for(int j=1;j<=k;++j){
			if(vc[j]&&a[j][wh[go]]){
				break;
			}
		}
			if(!v[go]&&!vc[wh[go]]){
				v[go]=1;vc[wh[go]]=1;
				dfs(go,y,stap+val[i]);
				v[go]=0;vc[wh[go]]=0;
			}
	}
}
int main(){
	scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
	for(int i=1;i<=n;++i)scanf("%d",&wh[i]);
	for(int i=1;i<=k;++i){
		for(int j=1;j<=k;++j)
		scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=m;++i){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	v[s]=1,vc[wh[s]]=1;
	dfs(s,t,0);
	if(ans==1000000)printf("-1");
	else printf("%d",ans);
	return 0;
}