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

using namespace std;

inline int read() {
	char c = getchar(); int x = 0, f = 1;
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar();}
	while (c <='9' && c >='0') { x = x * 10 + c - '0'; c = getchar();}
	return x * f;
}

int n, m, k, s, t, uu, vv, ww;
bool v[110][110];
int a[110][110];
int c[110];

int main() {
	freopen("culture.in", "r", stdin);
	freopen("culture.out", "w", stdout);
	n = read(), k = read(), m = read(), s = read(), t = read();
	for (register int i = 1; i <= n; i ++)
		c[i] = read();
	for (register int i = 1; i <= k; i ++)
		for (register int j = 1; j <= k; j ++)
			cin >> v[i][j];
	if (c[s] == c[t]) { printf("-1\n"); return 0;}
	for (register int i = 1; i <= n; i ++)
		for (register int j = 1; j <= n; j ++)
			a[i][j] = 2e7;
	for (register int i = 1; i <= m; i ++) {
		uu = read(), vv = read(), ww = read();
		if (!v[c[vv]][c[uu]] && c[vv] != c[uu]) a[uu][vv] = min(a[uu][vv], ww);
		if (!v[c[uu]][c[vv]] && c[vv] != c[uu]) a[vv][uu] = min(a[vv][uu], ww);
	}
	for (register int k = 1; k <= n; k ++)
		for (register int i = 1; i <= n; i ++)
		if (k != i)
			for (register int j = 1; j <= n; j ++)
			if (j != k && j != i)
				a[k][i] = min(a[k][i], a[j][i] + a[k][j]);
	if (a[s][t] == 2e7) { printf("-1\n"); return 0;}
	printf("%d\n", a[s][t]);
	return 0;
}