#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int read() {
	int s=0,f=1;
	char ch=getchar();
	for( ; ch<'0'||ch>'9'; f=(ch=='-')?(-1):f,ch=getchar()) ;
	for( ; ch>='0'&&ch<='9'; s=(s<<1)+(s<<3)+(ch^48),ch=getchar()) ;
	return s*f;
}
int n,k,m,st,ed,tot,r[105],cul[105],dis[105],head,tail,res[105][105];
bool dislik[105][105];
struct edge {
	int to,vv,next;
} c[20001];
void add(int x,int y,int z) {
	c[tot]=(edge) {
		y,z,r[x]
	};
	r[x]=tot++;
}
struct oo {
	int now;
	int cul[105];
	oo() {
		cul[0]=0;
	}
} que[100005];
void bfs() {
	dis[st]=0;
	que[++tail].now=st;
	que[tail].cul[++que[tail].cul[0]]=cul[st];
	while(head<tail) {
		oo sta=que[++head];
		for(int i=r[sta.now]; ~i; i=c[i].next) {
			if(dis[c[i].to]>dis[sta.now]+c[i].vv) {
				bool check=true;
				oo ans;
				for(int j=1; j<=sta.cul[0]&&check; ++j) {
					ans.cul[j]=sta.cul[j];
					if(dislik[cul[c[i].to]][sta.cul[j]]) {
						check=false;
					}
				}
				if(check) {
					ans.now=c[i].to,ans.cul[0]=sta.cul[0]+1;
					ans.cul[ans.cul[0]]=cul[c[i].to];
					dis[c[i].to]=dis[sta.now]+c[i].vv;
					que[++tail]=ans;
				}
			}
		}
	}
}
void bfs2() {
	dis[st]=0;
	que[++tail].now=st;
	while(head<tail) {
		oo sta=que[++head];
		for(int i=r[sta.now]; ~i; i=c[i].next) {
			if(dis[c[i].to]>dis[sta.now]+c[i].vv) {
				oo ans;
				dis[c[i].to]=dis[sta.now]+c[i].vv;
				ans.now=c[i].to;
				que[++tail]=ans;
			}
		}
	}
}
bool pd=true;
int Main() {
	freopen("culture.in","r",stdin);
	freopen("culture.out","w",stdout);
	n=read(),k=read(),m=read(),st=read(),ed=read();
	memset(r,0xff,sizeof(r));
	memset(dis,0x5f,sizeof(dis));
	memset(res,0x5f,sizeof(res));
	for(int i=1; i<=n; cul[i]=read(),++i) ;
	for(int i=1; i<=k; ++i) {
		for(int j=1; j<=k; ++j) {
			dislik[i][j]=read();
			if(dislik[i][j]) {
				pd=false;
			}
		}
		dislik[i][i]=true;
	}
	for(int x,y,z,i=1; i<=m; ++i) {
		x=read(),y=read(),z=read();
		res[y][x]=res[x][y]=min(res[x][y],z);
	}
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			if(res[i][j]!=1600085855) {
				add(i,j,res[i][j]);
			}
		}
	}
	if(!pd) {
		bfs();
	} else {
		bfs2();
	}
	printf("%d",(dis[ed]==1600085855)?(-1):dis[ed]);
	return 0;
}
int heh=Main();
int main() {
}