#include<bits/stdc++.h>
using namespace std;
int num,n,k,m,s,t,a[105],c[105][105],d[10005][10005],minn=1000000005;
void dfs(int aa,int bb)
{
	if(num==0&&minn>bb) minn=bb; 
	else
	{
		for(int i=1;i<=n;i++)
	    {
		    if(a[i]!=a[aa]&&d[aa][a[i]]!=1&&i!=aa)
		    {
		    	num--;
		        dfs(i,bb+c[aa][i]);
		        num++;
		    }
		    
	    }
	}
	return ;
}
int main()
{
	cin>>n>>k>>m>>s>>t;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=k;i++)
		for(int j=1;j<=k;j++)
		{
			int x;
			cin>>x;
			if(x==1) d[i][j]=1;
		}
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		c[x][y]=z;
	}
	num=n;
	dfs(1,0);
	if(minn==1000000005) cout<<-1<<endl;
	else cout<<minn<<endl;
	return 0;
}