#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define up(i,j,k,l) for(int i=j;i<=k;i+=l)
#define down(i,j,k,l) for(int i=j;i>=k;i-=l)
using namespace std;
const int N=1e2+10;
int n,k,m,s,t;
int c[N],a[N][N],p[N][N],z[N];
bool f[N];
int ans;
bool check(int x)
{
	up(i,1,n,1){
		if(a[c[x]][i] && z[i]>0){
			return false;
		}
	}
	return true;
} 
void dfs(int u,int ct)
{
	//cout<<u<<endl;
	if(u==t){
		//cout<<"DDD"<<endl;
		ans=min(ans,ct);
		//cout<<ans<<' '<<ct<<endl;
		return;
	}
	z[c[u]]++;
	f[u]=true;
	up(i,1,n,1){
		if(p[u][i]!=INT_MAX && f[i]==false && check(i)){
			//cout<<u<<' '<<i<<' '<<p[u][i]<<endl;
			dfs(i,ct+p[u][i]);
		}
	}
	f[u]=false;
	z[c[u]]--;
	return;
}
void solve()
{
	cin>>n>>k>>m>>s>>t;
	up(i,1,n,1){
		cin>>c[i];
	}
	up(i,1,k,1){
		up(j,1,k,1){
			cin>>a[i][j];
		}
	}
	int u,v,d;
	up(i,0,N-1,1){
		up(j,0,N-1,1){
			p[i][j]=INT_MAX;
		}
	}
	up(i,1,m,1){
		cin>>u>>v>>d;
		p[u][v]=min(p[u][v],d);
	}
	ans=INT_MAX;
	dfs(s,0);
	if(ans!=INT_MAX){
		cout<<ans;
	}
	else{
		cout<<-1;
	}
    return;
}
int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int _=1;
    //cin>>_;
    while(_--){
        solve();
    }
    return 0;
}