#include<queue>
#include<cstdio>
#include<cstring>
#define maxn 110

using namespace std;

int n,k,m,s,t,cnt;
int head[10010],d[maxn],c[maxn],a[maxn][maxn];

struct edge{int y,w,nxt;}e[20010];
void add(int x,int y,int w){e[++cnt].y=y;e[cnt].w=w;e[cnt].nxt=head[x];head[x]=cnt;}
struct node{int s,d;bool operator <(const node &a)const{return d>a.d;}};
priority_queue<node>q;

void dij(){
	d[s]=0;q.push((node){s,0});
	while(!q.empty()){
		node f=q.top();q.pop();
		int x=f.s;
		for(int i=head[x];i;i=e[i].nxt){
			int y=e[i].y,w=e[i].w;
			if(f.d!=d[x])continue;
//			printf("%d %d %d %d %d\n",x,y,c[x],c[y],a[c[y]][c[x]]);
			if(d[y]>d[x]+w&&(!a[c[y]][c[x]])){
				d[y]=d[x]+w;a[c[x]][c[x]]=1;
				q.push((node){y,d[y]});
			}
		}
	}
}

int main(){
	freopen("culture.in","r",stdin);
	freopen("culture.out","w",stdout);
	scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	if(c[s]==c[t])return printf("-1"),0;
	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,w;scanf("%d%d%d",&x,&y,&w);
		add(x,y,w);add(y,x,w);
	}
	memset(d,0x3f,sizeof(d));
	dij();
	if(d[t]==0x3f3f3f3f)printf("-1");
	else printf("%d",d[t]);
	return 0;
}
/*
6 3 8 2 5
1 2 3 1 2 3
0 0 1
0 1 1
1 0 0
1 3 2
1 4 5
2 6 3
2 5 14
3 4 2
2 3 8
4 5 8
1 6 5
*/