#include<bits/stdc++.h>
using namespace std;
struct ST{
	int v,len;
};
struct QT{
	int k,s;
};
int n,m,K,s,t,u,v,d,c[105],_k;
bool k[105][105],vis[105];
vector<ST>G[10005];
queue<QT>q;
int main(){
	cin>>n>>K>>m>>s>>t;
	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>>_k;
			if(_k==1)k[i][j]=true;
		}
	for(int i=1;i<=m;i++){
		cin>>u>>v>>d;
		G[u].push_back({v,d});
		G[v].push_back({u,d});
	}
	vis[c[s]]=true;
	q.push({s,0});
	while(!q.empty()){
		QT f=q.front();q.pop();
		if(f.k==t){
			cout<<f.s;
			return 0;
		}
		for(int i=0;i<G[f.k].size();i++){
			ST tk=G[f.k][i];
			if(!vis[c[tk.v]]&&!k[c[tk.v]][c[f.k]]){
				vis[c[tk.v]]=true;
				q.push({tk.v,f.s+tk.len});
			}
		}
	}
	cout<<-1;
	return 0;
}