#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,w;
	edge *n;
}a[20005],*pre[105];
int tot;
inline void insert(int s,int e,int w){
	a[++tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=&a[tot];
}
int n,k,m,s,t;
int c[105];
bool pc[105][105],vis[105];
int dis[105];
int tmp[105],top;
inline bool check(int u){
	if(vis[u])
		return false;
	for(int i=1;i<=top;++i)
		if(pc[c[u]][c[tmp[i]]])
			return false;
	return true;
}
inline void dfs(int u){
	if(dis[u]>=dis[t])
		return;
	if(u==t)
		return;
	for(edge *i=pre[u];i;i=i->n){
		int e(i->e),w(i->w);
		if(dis[e]>dis[u]+w&&check(e)){
			dis[e]=dis[u]+w;
			vis[e]=1;
			tmp[++top]=e;
			dfs(e);
			vis[e]=0;
			--top;
		}
	}
}
int inf;
inline int gg(){
	freopen("culture.in","r",stdin);
	freopen("culture.out","w",stdout);
	memset(dis,0x3f,sizeof(dis));
	inf=dis[1];
	memset(pre,NULL,sizeof(pre));
	n=read(),k=read(),m=read(),s=read(),t=read();
	for(int i=1;i<=n;++i)
		c[i]=read();
	for(int i=1;i<=k;++i)
		for(int j=1;j<=k;++j)
			pc[i][j]=read();
	for(int i=1;i<=m;++i){
		int x(read()),y(read()),z(read());
		insert(x,y,z),insert(y,x,z);
	}
	if(pc[t][s]){
		puts("-1");
		return 0;
	}
	dis[s]=0;
	vis[s]=1;
	tmp[++top]=s;
	dfs(s);
	printf("%d",dis[t]==inf?-1:dis[t]);
	return 0;
}
int K(gg());
int main(){;}