#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>

#define maxn 110
#define maxe 10010
#define INF 0x3f3f3f3f

using namespace std;

inline int read(){
	int op=1,aa=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')op=-1;c=getchar();}
	while(c>='0'&&c<='9'){aa=aa*10+c-'0';c=getchar();}
	return op*aa;
}

int c[maxn];
int n,k,m,s,t;
bool a[maxn][maxn];

int cnt;
int w[maxe];
int to[maxe];
int nxt[maxe];
int head[maxn];

inline void add_edge(int u,int v,int d){
	cnt++;
	w[cnt]=d;
	to[cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

int dis[maxn];
bool vis[maxn];
vector<int>cul;

struct node{
	int u,d;
	bool operator <(const node &temp)const{
		return d>temp.d;
	}
};
priority_queue<node>q;

bool check(int tc){
	for(int i=0;i<cul.size();i++)
		if(a[tc][cul[i]])return true;
	return false;
}

void dijkstra(int s){
	for(int i=1;i<=n;i++)dis[i]=INF;
	dis[s]=0;
	q.push((node){s,0});
	while(!q.empty()){
		node temp=q.top();q.pop();
		int u=temp.u;
		if(vis[u])continue;
		vis[u]=1;
		cul.push_back(c[u]);
		for(int i=head[u];i;i=nxt[i]){
			int v=to[i];
			if(vis[v]||check(c[v]))continue;
			if(dis[u]+w[i]<dis[v])dis[v]=dis[u]+w[i],cul.push_back(c[u]);
			if(!vis[v])q.push((node){v,dis[v]});
		}
	}
}

int main(){
	freopen("culture.in","r",stdin);
	freopen("culture.out","w",stdout);
	n=read(),k=read(),m=read(),s=read(),t=read();
	for(register int i=1;i<=n;i++)c[i]=read();
	for(register int i=1;i<=k;i++)
		for(register int j=1;j<=k;j++)
			a[i][j]=read();
	for(register int i=1;i<=m;i++){
		int u=read(),v=read(),d=read();
		add_edge(u,v,d);add_edge(v,u,d);
	}
	dijkstra(s);
	if(dis[t]==INF)printf("-1\n");
	else printf("%d\n",dis[t]);
	return 0;
}