#10就是tle。。。

#include <iostream>
#include <vector>
using namespace std;
const int MAXN(105),MAXK(105);
int c[MAXN];
bool a[MAXK][MAXK];
struct Node{
  int v, w;
  Node(int v, int w):v(v), w(w){}
};
vector<Node> g[MAXN];
bool vis[MAXK];
int n, k, m, s, t;
int ans(0x3f3f3f3f);
void dfs(int u, int sum){
  if(u == t){
    ans = min(ans, sum);
    return;
  }
  for(auto &item : g[u]){
    if(!vis[c[item.v]]){
      if(item.w + sum > ans) continue;
      if(item.v != t && c[item.v] == c[t]) continue;
      
      vis[c[item.v]] = true;
      dfs(item.v, sum + item.w);
      vis[c[item.v]] = false;
    }
  }
}
int main(){
	cin >> n >> k >> m >> s >> t;
  for(int i = 1; i <= n; i++){
    cin >> c[i];
  }
  for(int i = 1; i <= k; i++){
    for(int j = 1; j <= k; j++){
      cin >> a[i][j];
    }
  }
  while(m--){
    int u, v, w;
    cin >> u >> v >> w;
    int cu = c[u];
    int cv = c[v];
    if(cu == cv) continue;
    if(!a[cv][cu]){
    	g[u].push_back(Node(v, w));  
    }
    if(!a[cu][cv]){
    	g[v].push_back(Node(u, w));  
    }
  }
  if(c[s] == c[t]){
    cout << -1;
    return 0;
  }
  vis[c[s]] = true;
  dfs(s, 0);
  if(ans == 0x3f3f3f3f){
    cout << -1;
  }else{
    cout << ans;
  }
  return 0;
}