#include <algorithm> 
#include <bitset> 
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex> 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque> 
#include <exception>
#include <fstream>
#include <functional> 
#include <limits>
#include <list> 
#include <map> 
#include <iomanip>
#include <ios> 
#include <iosfwd> 
#include <iostream>
#include <istream> 
#include <ostream>
#include <queue> 
#include <set> 
#include <sstream> 
#include <stack> 
#include <stdexcept> 
#include <streambuf> 
#include <string> 
#include <utility> 
#include <vector> 
#include <cwchar>
#include <cwctype>
using namespace std;
inline int read()
{
	char ch=getchar();int x=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
const int maxn=10005;
const int inf=1e9+1;
int n,k,m,s,t;
int cul[maxn],head[maxn],tot,dis[maxn];
bool check[maxn][maxn],vis[maxn],judge[maxn];
struct Edge
{
	int from,to,nxt,w;
}e[maxn];
void add(int x,int y,int w)
{
	e[++tot].from=x;e[tot].to=y;e[tot].nxt=head[x];e[tot].w=w;head[x]=tot;
}
void dij()
{
	if(check[t][s]){cout<<"-1";return;}
	judge[cul[s]]=1;
	for(int i=1;i<=n;i++)dis[i]=inf;
	dis[s]=0;
	int u=s;
	while(!vis[u])
	{
		vis[u]=1;
		for(int i=head[u],w,v;i;i=e[i].nxt)
		{
			v=e[i].to,w=e[i].w;
			if(dis[v]>dis[u]+w&&!check[v][u])
			{
				dis[v]=dis[u]+w;
				judge[cul[v]]=1;
			}
		}
		int minn=inf;
		for(int i=1;i<=n;i++)
		{
			if(vis[i])continue;
			if(dis[i]<minn)
			{
				u=i;
				minn=dis[i];
			}
		}
	}
	if(dis[t]==inf)
	{
		cout<<"-1";
		return ;
	}
	else 
	{
		cout<<dis[t];
		return ;
	}
}
int main()
{
	freopen("culture.in","r",stdin);
	freopen("culture.out","w",stdout);
	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";
		return 0;
	}
	for(int i=1;i<=k;i++)
	{
		for(int j=1;j<=k;j++)
		{
			int a=read();
			if(a)check[i][j]=1;
		}
	}
	while(m--)
	{
		int x=read(),y=read(),w=read();
		if(!check[y][x]&&!check[x][s])
		add(x,y,w);
		if(!check[x][y]&&!check[y][s])
		add(y,x,w);
	}
	dij();
	return 0;
}