#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,k,s,t;
int c[105];
int a[105][105];
vector<pair<int,int> > edge[10005];
int d[105];
bool vis[105];
priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > pq;
bool check(int point){
	for (int i=1;i<=n;i++){
		if (vis[i]&&a[c[point]][c[i]]==1) return false;
	}
	return true;
}
void dijkstra(){
	memset(d,INF,sizeof(d));
	d[s]=0;
	pq.push(make_pair(0,s));
	while (!pq.empty()){
		pair<int,int> neww=pq.top();
		pq.pop();
		int u=neww.second;
		if (vis[u]) continue;
		vis[u]=true;
		for (int i=0;i<edge[u].size();i++){
			int v=edge[u][i].first,w=edge[u][i].second;
			if (!vis[v]&&d[u]+w<d[v]&&check(v)){ 
				d[v]=d[u]+w;
				pq.push(make_pair(d[v],v));
			}
		}
	}
}
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);
		edge[u].push_back(make_pair(v,d));
		edge[v].push_back(make_pair(u,d));
	}
	dijkstra();
	if (d[t]==INF){
		printf("%d\n",-1);
	}
	else printf("%d\n",d[t]);
	return 0;
}