#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
int read(){
    int w=1,x=0,ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')w=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*w;
}
int n,k,m,S,T;
const int MAXN = 110;
const int EMAXN = 110*110;
int C[MAXN];//???????
struct Eage {
    int from,to,val,nxt;
    Eage(int from,int to,int val,int nxt){
        this->from=from;
        this->to=to;
        this->val=val;
        this->nxt=nxt;
    }
    Eage(){}
}E[EMAXN<<1];
int head[MAXN],tot;
void add(int from,int to,int val){
    E[++tot]=Eage(from,to,val,head[from]),head[from]=tot;
}
bool repulsion[MAXN][MAXN];//? ? ?
int minv[MAXN][MAXN];
const int INF = 0x3f3f3f3f;
struct Node{
    bool culture[MAXN];
    int dist,id;
    Node(int dist,int id,bool *culture){
        this->dist=dist;
        this->id=id;
        memcpy(this->culture,culture,sizeof(this->culture));
    }
    Node(){}
    bool operator <(const Node &x)const{return this->dist>x.dist;}
};
priority_queue<Node>q;
int d[MAXN];
bool outque[MAXN];
void Spfa(){
    memset(d,0X3f,sizeof(d));
    d[S]=0;
    bool culture1[MAXN];
    memset(culture1,0,sizeof(culture1));
    culture1[C[S]]=1;
    q.push(Node(0,S,culture1));
    while(!q.empty()){
        Node x=q.top();
        q.pop();
        if(outque[x.id])continue;
        outque[x.id]=true;
        for(int i=head[x.id];i;i=E[i].nxt){
            int to=E[i].to;
//            for(int i=1;i<=k;i++)cout<<x.culture[i]<<" ";
//            cout<<endl;
            if(x.culture[C[to]])continue;
            bool flag=false;
//	    	cout<<to<<endl;
//            cout<<repulsion[x.culture[C[S]]][C[to]]<<" "<<"qwq"<<endl;
            for(int j=1;j<=k;j++)if(x.culture[j]&&repulsion[j][C[to]]){flag=true;break;};
            if(flag)continue;
            if(d[x.id]+E[i].val>d[to])continue;
            d[to]=d[x.id]+E[i].val;
           	bool tmp[MAXN];
			memcpy(tmp,x.culture,sizeof(tmp));
			tmp[C[to]]=true;
            q.push(Node(d[to],to,tmp));
        }
    }
}
int main(){
	freopen("culture.in","r",stdin);
	freopen("culture.out","w",stdout);
    n=read(),k=read(),m=read(),S=read(),T=read();
    for(int i=1;i<=n;i++)C[i]=read();
    memset(repulsion,0,sizeof(repulsion));
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
            repulsion[j][i]=read();
//    cout<<repulsion[1][2]<<endl;
//    cout<<repulsion[2][1]<<endl;
    memset(minv,0x3f,sizeof(minv));
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),d=read();
        minv[u][v]=min(minv[u][v],d);
        minv[v][u]=min(minv[v][u],d);
    }
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(minv[i][j]!=INF)
                add(i,j,minv[i][j]),
                add(j,i,minv[i][j]);
    Spfa();
//    for(int i=head[S];i;i=E[i].nxt)cout<<E[i].to<<" "<<repulsion[S][E[i].to]<<endl;
    if(d[T]!=INF)printf("%d",d[T]);
    else printf("-1");
    return 0;
}
/*
*/