#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=101,M=10001,inf=0x3f3f3f3f;
struct Edge{
    int to,w,nxt;
}e[M<<1];
struct Node{
	int u,dis;
	inline bool operator<(const Node &rhs) const {
		return dis>rhs.dis;
	}
};
int cul[N],hd[N],vis[N],dis[N],n,k,s,t,cnt,ans=inf;
bool pc[N][N];
inline void add(int u,int v,int w){
    e[++cnt]={v,w,hd[u]},hd[u]=cnt;
}
void dijkstra(){
	priority_queue<Node> q;
	memset(dis,0x3f,sizeof(dis));
	q.push({s,dis[s]=0});
	while(q.size()){
		int u=q.top().u;q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=hd[u];i;i=e[i].nxt){
			int v=e[i].to,w=e[i].w;
			if(dis[u]+w<dis[v]){
				q.push({v,dis[v]=dis[u]+w});
			}
		}
	}
}
void dfs(int u,int cur){
	//printf("dfs %d %d\n",u,dis);
	if(cur+dis[u]>=ans){
		return;
	}
	if(u==t){
		ans=min(ans,cur);
		return;
	}
    ++vis[cul[u]];
    for(int i=1;i<=k;++i){
    	if(pc[i][cul[u]]){
    		++vis[i];
		}
	}
    for(int i=hd[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].w;
        if(vis[cul[v]]||cur+w>=ans){
        	continue;
		}
        dfs(v,cur+w);
    }
    for(int i=1;i<=k;++i){
    	if(pc[i][cul[u]]){
    		--vis[i];
		}
	}
    --vis[cul[u]];
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
    int m,u,v,w;
    cin>>n>>k>>m>>s>>t;
    for(int i=1;i<=n;++i){
    	cin>>cul[i];
    }
    for(int i=1;i<=k;++i){
        for(int j=1;j<=k;++j){
        	cin>>pc[i][j];
        }
    }
    while(m--){
    	cin>>u>>v>>w;
        add(u,v,w),add(v,u,w);
    }
    dijkstra();
    memset(vis,0,sizeof(vis));
    dfs(s,0);
    if(ans==inf) cout<<"-1";
    else cout<<ans;
    return 0;
}

#10 过不了，92pts。已经按照题解一的方法剪枝了。