#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int N,K,M,S,T;
int C[101];
bool a[101][101];
//链式前向星
struct Edge{
	int v,d;
	int next;
}edge[10001];
int cnt=1,head[101]={};
void addedge(int u,int v,int d){
	edge[cnt].v=v;
	edge[cnt].d=d;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
//dijkstra
struct node{
	int order,value;
	bool wh[101];
	bool operator <(const node &other)const{
		return value>other.value;
	}
};
int dis[101]={};
bool vis[101]={};
priority_queue<node>q;
void dijkstra(){
	memset(dis,1001,sizeof(dis));
	node s;
	s.order=S;
	s.value=0;
	s.wh[C[S]]=true;
	q.push(s);
	while(!q.empty()){
		printf(".");
		node top=q.top();
		q.pop();
		if(vis[top.order])continue;
		vis[top.order]=true;
		dis[top.order]=top.value;
		for(int i=head[top.order];i!=0;i=edge[i].next,printf("."))
			if(C[top.order]!=C[edge[i].v]&&!a[C[top.order]][C[edge[i].v]]){
				node n;
				n.order=edge[i].v;
				n.value=dis[top.order]+edge[i].d;
				memcpy(top.wh,n.wh,sizeof(top.wh));
				n.wh[C[n.order]]=true;
				q.push(n);
			}
	}
}
int main(){
	scanf("%d%d%d%d%d",&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]);
	for(int i=1;i<=M;i++){
		int u,v,d;
		scanf("%d%d%d",&u,&v,&d);
		addedge(u,v,d);
		addedge(v,u,d);
	}
	if(a[C[S]][C[S]])printf("-1");
	else{
		dijkstra();
		if(dis[T]!=1001)printf("%d",dis[T]);
		else printf("-1");
	}
	return 0;
}