#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e2+10,K=1e2+10,M=N*N,inf=0x3f3f3f3f;
int n,kk,m,s,t,e,x,u,v,d,ans=inf;
int c[N],Begin[N],Next[2*M],To[2*M],W[2*M],dis[N];
set<int>cur;
bool a[K][K],vis[N];
struct Node{
	int id,val;
	friend bool operator<(Node a,Node b){
		return a.val>b.val;
	}
}f;
priority_queue<Node>q;
void dij(){
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	q.push((Node){s,0});
	while(!q.empty()){
		f=q.top();
		q.pop();
		if(vis[f.id])continue;
		//printf("now dij %d ,val %d\n",f.id,f.val);
		vis[f.id]=1;
		for(int i=Begin[f.id];i;i=Next[i]){
			if(dis[To[i]]>dis[f.id]+W[i]){
				dis[To[i]]=dis[f.id]+W[i];
				q.push((Node){To[i],dis[To[i]]});
			}
		}
	}
	return ;
}
void add(int x,int y,int z){
	To[++e]=y;
	W[e]=z;
	Next[e]=Begin[x];
	Begin[x]=e;
	return ;
}
bool check(int cl){
	for(auto v:cur)
		if(a[v][cl])
			return 0;
	return 1;
}
void dfs(int now,int dd){//dfs倒着从终点回到起点
	//printf("now dfs %d %d\n",now,dd);
	vis[now]=1;
	cur.insert(c[now]);//学会now国家的文化
	if(now==s){//到达起点
		ans=min(ans,dd);
		return ;
	}
	if(dd+dis[now]>ans)//剪枝,考虑文化排斥一定小于等于不考虑
        return ;
	for(int i=Begin[now];i;i=Next[i])
		if(!vis[To[i]]&&check(c[To[i]]))
			dfs(To[i],dd+W[i]);

	vis[now]=0;//回溯
	cur.erase(c[now]);
	return ;
}
void print1(){
	for(int i=1;i<=n;++i)
		printf("%d:%d\n",i,dis[i]);
}
int main(){
	scanf("%d %d %d %d %d",&n,&kk,&m,&s,&t);
	for(int i=1;i<=n;++i)
		scanf("%d",c+i);
	for(int i=1;i<=kk;++i)
		for(int j=1;j<=kk;++j)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=m;++i){
		scanf("%d %d %d",&u,&v,&d);
		add(u,v,d);
		add(v,u,d);
	}
	dij();
	//print1();
	if(dis[t]==inf){
		puts("-1");
		return 0;
	}
	memset(vis,0,sizeof vis);
	dfs(t,0);
	if(ans==inf)
		puts("-1");
	else
		printf("%d\n",ans);
	return 0;
}

看输入是咋输入的就能看懂，dij是跑了个笛孑斯特拉，dfs是从终点往起点搜索，check函数判断文化是否排斥。