#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>

using namespace std;
int n,k,m,s,t,dis[105],cnt,tot,head1[10004],head2[10004],kind[1005],a[105][105];
struct node {
	int u,d;
};                   

inline bool operator < (node a,node b) {
	return a.d > b.d;                     
}
priority_queue <node> q;
struct EDGE{
	int to,nxt;
}e[10004];

struct edge{
	int to,nxt,d;
}ed[10004];


void add1(int x,int y,int d)
{
	tot++;
	ed[tot].d=d;
	ed[tot].nxt=head2[x];
	ed[tot].to=y;
	head2[x]=tot;
	//cout<<head2[x]<<endl;
	
}
int dij(int s) {
	for(int i=0; i<=n; i++) dis[i] = 0x7fffffff;   
	dis[s] = 0;
	q.push( (node) {
		s,0
	} );                  
	while( !q.empty() ) {
		node from = q.top();
		q.pop();      
		int u = from.u;
		
         
		for(int i=head2[u]; i; i=ed[i].nxt) { 
			int v = ed[i].to;
			int w = ed[i].d;
			if(dis[u]!=from.d)
			continue;
			if(dis[v] > dis[u] + w&&!a[kind[v]][kind[u]]) {
				dis[v] = dis[u] + w;       

				q.push( (node) {
					v,dis[v]
				} );
			}
		}
	}
	
}

int main()
{ freopen("culture.in","r",stdin);
    freopen("culture.out","w",stdout);
   cin>>n>>k>>m>>s>>t;
	for(int i=1;i<=n;i++)
	{
		cin>>kind[i];
	}
	
   for(int i=1;i<=k;i++)
   {
   for(int j=1;j<=k;j++)
   {
   	int x;
   	cin>>x;
   	
   	a[i][j]=x;
   }
   	
   }

	for(int i=1;i<=m;i++)
	{
		int u,v,d;
		cin>>u>>v>>d;
		add1(u,v,d);
		add1(v,u,d);
/*	for(int i=head1[u];i;i=e[i].nxt)
		{
			int t=e[i].to;
			if(t==v)
			continue;
			else add1(u,v,d);
		}
		for(int i=head1[v];i;i=e[i].nxt)
		{
			int t=e[i].to;
			cout<<t<<endl;;
			if(t==u)
			continue;
			else add1(v,u,d);
		}*/
	
	}


    dij(s);
    if(kind[s]==kind[t])
    {
    	cout<<"-1";
    	return 0;
	}
    if(dis[t]!=0x7fffffff)
    cout<<dis[t];
    
    else {
    	cout<<"-1";
	}
	
	return 0;
}