#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
 
const int MAXN = 105;
int n, k, m, s, t;
int c[MAXN];       // c[i] 记录第i个国家的文化；
int a[MAXN][MAXN]; // a[i][j]=1 表示第i种文化对第j种文化排斥。0表示不排斥
int e[MAXN][MAXN]; // e[i][j]=d 表示第i个国家到第j个国家之间有一条边，长度为d
int dis[MAXN];     // dis[i] 记录从起点国到第i个国家的最短距离
bool vis[MAXN];    // vis[i] = true 表示第i种文化已经学过
 
/*
深搜dfs：
1、从起点国家开始，dfs每一个国家到起点国家的最短距离。
2、向下dfs时的判断规则为（X为当前国家，i为下一个国家）
a. 如果 x,i 两国之间没有路，则不走
b. 如果 i 国文化已经学过，则不走
c. 如果 i 国文化对 x 国文化排斥，则不走
入参：x为当前国家：d为x国到起点国的最短距离
*/
void dfs(int x, int d)
{
    if (d >= dis[x])  return;	// 如果x国当前传进来的距离d大于之前算过的最短距离 dis[x]， 则返回，不再计算后续路径
    dis[x] = d; // 否则，更新x国到起点国的最段距离
 
    // 继续向下深搜dfs
    if (x == t) return; // 如果当前已达到终点国，则不继续深搜
    for (int i = 1; i <= n; i ++)
    {				    // 否则，枚举每一个国家 i
        if( e[x][i] == INF ) continue;  // 如果x,i两国之间没有路，则枚举下一个国家
        if( vis[c[i]] == true ) continue;       // 如果 i 国文化已经学过，则枚举下一个国家
        if( a[c[i]][c[x]] == 1 )  continue; // 如果 i 国文化对 x 国文化排斥，则枚举下一个国家
 
        vis[c[i]] = true;  // 对 i 国深搜之前，先标记该国文化为已访问
        dfs(i, d + e[x][i]);
        vis[c[i]] = false; // 推出dfs时恢复现场
	}
}
 
 
int main()
{
    scanf("%d %d %d %d %d", &n, &k, &m, &s, &t);
    for(int i = 1; i <= n; i++)  scanf("%d", &c[i]);   //国家 i的文化为 Ci
    for(int i = 1; i <= k; i++)
        for(int j = 1; j <= k; j++)
            scanf("%d", &a[i][j]);  //a[i][j] = 1 表示文化 i 排斥外来文化 j
 
    memset(dis, 0x3f, sizeof(dis)); // 初始化每个国家到起点国的最短距离为正无穷
    memset(e, 0x3f, sizeof(e));     // 初始化国与国之间的边为正无穷
 
    for(int i = 1; i <= m; i++)
    {
        int u, v, d;
        scanf("%d %d %d", &u, &v, &d);
        e[u][v] = min(e[u][v], d);  // 邻接矩阵:由于两个国家之间可能有多条道路，所以读入时取最小值存边
        e[v][u] = min(e[v][u], d);  // 邻接矩阵:由于两个国家之间可能有多条道路，所以读入时取最小值存边
    }
 
    vis[c[s]] = true; // 起点国的文化标记为已学过
    dfs(s, 0);        // 从起点国s进行深搜，当前最短距离为0
 
    if (dis[t] == INF)  printf("-1\n");
    else  printf("%d\n", dis[t]);
 
    return 0;
}