#include<bits/stdc++.h>
using namespace std;
int n,k,m,s,t,minn=INT_MAX;
int kk[200][200],c[200],u[10010],v[10010],d[10010],f[10100];
void dfs(int s1,int sum){
    if(s1==t){
        minn=min(minn,sum);
        return ;
    }
    if(sum>=minn) return ;
    for(int i=1;i<=m;i++){
        if(s1==u[i]&&f[v[i]]==-1&&kk[v[i]][u[i]]==0){
            f[s1]==0;
            dfs(v[i],sum+d[i]);
            f[s1]=-1;
        }
    }
}
int main(){
    cin>>n>>k>>m>>t>>s;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=k;i++){
        for(int j=1;j<=k;j++){
            cin>>kk[i][j];
        }
    }
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>d[i];

    }
    dfs(s,0);
    if(minn==INT_MAX)cout<<"-1";
    else cout<<minn;
    return 0;
}