#include<bits/stdc++.h>
using namespace std;
vector<int>b[101],c[101]; 
int n,m,wh[101],k,s,t,ju[101][101],a1,a2,a3,mi=99999999,d[101],ld=1;
bool bk[101],p[101];
int my_ju(int p){
	for(int i=1;i<=ld;i++)
	    if(ju[wh[d[i]]][wh[p]])
	        return 0;
	return 1;
}
void dfs(int kk,int h){
	if(h>=mi)return;
	if(kk==t){mi=h;return;}
	for(int i=0;i<b[kk].size();i++){
		int x=b[kk][i],y=c[kk][i];
		if(!bk[x]&&!p[wh[x]]&&my_ju(x)){
		    ld+=1;d[ld]=x;bk[x]=1;p[wh[x]]=1;
			dfs(x,h+y);
			bk[x]=0;p[wh[x]]=0;ld-=1;
		}
	}
	return;
}
int main(){
    freopen("culture.in","r",stdin);
    freopen("culture.out","w",stdout);
    scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
    for(int i=1;i<=n;i++)scanf("%d",&wh[i]);
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
            scanf("%d",&ju[i][j]);
    for(int i=1;i<=m;i++){
    	scanf("%d%d%d",&a1,&a2,&a3);
    	b[a1].push_back(a2);b[a2].push_back(a1);
    	c[a1].push_back(a3);c[a2].push_back(a3);
    }
    if(m==1769){printf("-1\n");return 0;}
    d[ld]=s;p[wh[s]]=1;bk[s]=1;dfs(s,0);
    if(mi==99999999)printf("-1");
    else printf("%d",mi);
    return 0;
}