#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#define file(x) "culture."#x
using std::min;
using std::queue;
const int MAXK=105,MAXN=105; 
int n,k,m,d[MAXN][MAXN],s,t,c[MAXN],ans=1<<30;
bool dy[MAXN][MAXN];
struct NODE{
	bool pc[MAXK];
	int dis,u;
	NODE(int iu,int idis){memset(this,0,sizeof(*this));u=iu,dis=idis;}
};
queue<NODE> q;
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	int tmp;
	for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) scanf("%d",&tmp),dy[i][j]=tmp;
	for(int i=1;i<=m;i++) {
		int u,v;
		scanf("%d%d%d",&u,&v,&tmp);
		if(!d[u][v]) d[u][v]=d[v][u]=tmp;
		else d[u][v]=d[v][u]=min(d[u][v],tmp);
	}
	{
		int asd=s;
		s=t;
		t=asd;
	}
	NODE u(s,0);
	u.pc[c[s]]=1;
	q.push(u);
	while(!q.empty()){
		u=q.front();q.pop();
		if(u.u==t) {
			ans=min(ans,u.dis);
			continue;
		}
		if(u.dis>ans) continue;
		for(int v=1;v<=n;v++) if(d[u.u][v]&&!u.pc[c[v]]){
			bool f=0;
			for(int j=1;j<=k;j++) if(u.pc[j]&&dy[c[v]][j]) {
				f=1;
				break;
			}
			if(f) continue;
			NODE nu=u;
			nu.pc[c[v]]=1;
			nu.dis+=d[u.u][v];
			nu.u=v;
			q.push(nu);
		}
	}
	printf("%d",ans==1<<30?-1:ans);
}