#include <bits/stdc++.h>
using namespace std;
int n,k,m,s,e,c[10001],x,y,z,dis[10001]; 
bool v[1001],vi[200][10001],ag[1001][1001];
struct node{
	int x,w;
	node(int _x=0,int _w=0):x(_x),w(_w){}
};
struct nod{
	int x,w,adr;
	nod(int _x=0,int _w=0,int _adr=0):x(_x),w(_w),adr(_adr){}
	bool operator < (const nod&a)const{return w>a.w;}
};
vector<node>T[1001];
priority_queue<nod>que;
int main(){
	cin>>n>>k>>m>>s>>e;
	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>>ag[j][i];//i被j排斥 
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		T[x].push_back(node(y,z));
		T[y].push_back(node(x,z));
	}
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	int cnt=0;
	que.push(nod(s,0,++cnt));
	vi[cnt][s]=1;
	while(!que.empty())
	{
		int x=que.top().x,len=que.top().w,adr=que.top().adr;
		que.pop();
		if(v[x])continue;
		v[x]=1;
		for(int i=0;i<T[x].size();i++)
		{
			int u=T[x][i].x,w=T[x][i].w;
			bool flag=1;
			if(!v[u]&&len+w<dis[u])
			{
				for(int k=1;k<=n;k++)
					if(vi[adr][k]&&ag[c[k]][c[u]])flag=0;
				if(flag)
				{	
					dis[u]=w+len;
					que.push(nod(u,dis[u],++cnt));
					for(int i=1;i<=n;i++)vi[cnt][i]=vi[adr][i];
					vi[cnt][u]=1;
				}		
			}
		}
	}
//	for(int i=1;i<=n;i++)cout<<dis[i]<<endl;
	if(dis[e]==0x3f3f3f3f)cout<<-1;
	else cout<<dis[e];
    return 0;
}