#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=105;
struct node{
	int v,w;
};
struct nodee{
	int u,d;
	int used[N];//哪种语言使用过了 
	bool operator<(const nodee &A)const{
		return A.d<d;
	}
};
vector<node>edge[N];
bool vis[N],qs[N][N];
int dis[N],c[N];
int n,f,t,w,m,u,st,en,k,v;
void dijkstra(int st){
	priority_queue<nodee>q;
	nodee ccf;
	ccf.u=st;
	ccf.d=0;
	for(int i=1;i<=k;i++) ccf.used[i]=0;
	q.push(ccf);//封装存储 
	fill(dis,dis+1+n,1e9);//最大值初始化 
	dis[st]=0;
	while(!q.empty()){
		u=q.top().u;
		nodee us=q.top();
		q.pop();
		if(vis[u]||us.used[c[u]]) continue;
		vis[u]=1;
		us.used[c[u]]=1;
		for(int i=1;i<=k;i++)
			if(qs[c[u]][i]) us.used[i]=1;//歧视 
		for(node e:edge[u]){
			v=e.v;
			w=e.w;
			if(us.used[c[v]]) continue; 
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!vis[v]){
					ccf.d=dis[v];
					ccf.u=v;
					for(int j=1;j<=k;j++) ccf.used[j]=us.used[j];
					q.push(ccf);
				}
			}
		}
	}
	if(dis[en]!=1e9) cout<<dis[en];
	else cout<<-1;
	return ;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k>>m>>st>>en;
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++) cin>>qs[i][j];
	while(m--){
		cin>>f>>t>>w;
		edge[f].push_back(node{t,w});
		edge[t].push_back(node{f,w});
	}
	dijkstra(st);
	return 0;
}