#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define maxn (int)1e4+5
#define INF 0x3f3f3f3f


using namespace std;

inline int read()
{
    register int x=0,w=1,ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*w;
}

int n,m,k,s,t;
int tot,head[maxn],dis[maxn],c[105][105],cul[105];
bool vis[maxn];
vector<int>p;

struct Edge{
    int x,y,w,nxt;
}edge[maxn];

void add(int x,int y,int w)
{
    edge[++tot].x=x,edge[tot].y=y,edge[tot].w=w;
    edge[tot].nxt=head[x],head[x]=tot;
}

struct Node{
    int w,now;
    bool operator<(const Node &rhs)const{
        return w>rhs.w;
    }
};

bool check(int u,int v)
{
    for(int i=0;i<p.size();i++){
        //if(p[i]==cul[v])return false;
        if(c[cul[v]][p[i]]==1)return false;
    }
    if(c[cul[t]][cul[v]])return false;
    return true; 
}

void dijkstra()
{
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[s]=0;p.push_back(cul[s]);//,p.push_back(cul[t]);
    priority_queue<Node>q;
    q.push((Node){0,s});
    while(!q.empty()){
        Node x=q.top();
        q.pop();
        int u=x.now;
        if(vis[u])continue;
        vis[u]=true;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].y;
            if(dis[v]>dis[u]+edge[i].w&&check(u,v)==true){
                dis[v]=dis[u]+edge[i].w;
                p.push_back(cul[v]); 
                q.push((Node){dis[v],v});
            }
        }
    }
    printf("%d\n",dis[t]==INF?-1:dis[t]);
}

int main()
{
    freopen("culture.in","r",stdin);
    freopen("culture.out","w",stdout);
    int x,y,z;
    n=read(),k=read(),m=read(),s=read(),t=read();
    for(int i=1;i<=n;i++)cul[i]=read();
    if(cul[s]==cul[t]){cout<<"-1"<<'\n';return 0;}
    for(int i=1;i<=k;i++)
        for(int j=1;j<=k;j++)
        c[i][j]=read();
    while(m--){
        x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    dijkstra();	
    return 0;
}