//
//  main.cpp
//  IDE
//
//  Created by aa on 2023/2/26.
//

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=3e3+5;
bool vis[N];
int n,m,k,s,t,u,v,w;
int a[110][110];
int b[110][110];
int c[110];
bool use[110][110][110];
long long ans=0;
int minn(int x,int y){
	if(x<y){
		return x;
	}
	return y;
}
void IO(){
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
}
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(!a[c[k]][c[i]]
				   &&!a[c[k]][c[j]]
				   &&!use[i][k][c[j]]
				   &&!use[k][j][c[i]]
				   &&b[i][k]+b[k][k]<b[i][j]){
					for(int t=1;t<=n;t++){
						use[i][j][t]=(use[i][k][t]||use[k][j][t]);
						use[i][j][c[k]]=1;
						b[i][j]=b[i][k]+b[k][j];
					}
				}
			}
		}
	}
}
void inp(){
	cin>>n>>k>>m>>s>>t;
	memset(b,0x3f,sizeof b);
	for(int i=1;i<=n;i++){
		cin>>c[i];
		b[i][i]=0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		if(!a[c[v]][c[u]]&&c[u]!=c[v]){
			b[u][v]=minn(w,b[u][v]);
		}if(!a[c[u]][c[v]]&&c[u]!=c[v]){
			b[v][u]=minn(w,b[v][u]);
		}
	}
}void work(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			use[i][j][c[i]]=1;
			use[i][j][c[j]]=1;
		}
	}
	floyd();
	if(b[s][t]==0x3f3f3f3f){
		cout<<-1<<endl;
	}else{
		cout<<b[s][t]<<endl;
	}
}
int main() {
	IO();
    inp();
    work();
    return 0;
}