//spfa/dijkstra + dfs
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+10, M = 10e5+10;
typedef pair<int, int> PII;
int n, m, ans = 0x3f3f3f3f;
int a[6];
int x, y, t;
int h[N], e[2*M], ne[2*M], w[2*M], idx;
int dis[6][N];
bool v[N];
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
//被卡掉了
void spfa(int k){
int u = a[k];
memset(dis[k], 0x3f, sizeof dis[k]);
dis[k][u] = 0;
bool vis[N] = {false};
queue<int> q;
q.push(u), vis[u] = true;
while(!q.empty()){
int t = q.front();
q.pop(), vis[t] = false;
for(int i=h[t]; ~i; i=ne[i]){
int j = e[i];
if(dis[k][j] > dis[k][t]+w[i]){
dis[k][j] = dis[k][t]+w[i];
if(!vis[j]){
q.push(j);
vis[j] = true;
}
}
}
}
}
void h_dijkstra(int k){
int t = a[k];
memset(dis[k], 0x3f, sizeof dis[k]);
dis[k][t] = 0;
bool vis[N] = {false};
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, t});
while(q.size()){
PII tmp = q.top();
q.pop();
int v = tmp.second;
if(vis[v]) continue;
vis[v] = true;
for(int i=h[v]; ~i; i=ne[i]){
int u = e[i];
if(dis[k][u]>dis[k][v]+w[i]){
dis[k][u] = dis[k][v]+w[i];
q.push({dis[k][u], u});
}
}
}
}
// k 已经给几家亲戚拜过年了
// tt 已经花费的时间
// pre 拜访的前一家亲戚在 a[] 中的下标
void dfs(int k, int tt, int pre){
if(tt>=ans) return ;
if(k==5){
ans = min(ans, tt);
return ;
}
for(int i=1; i<=5; i++){
int j = a[i];
if(!v[j]){
v[j] = true;
dfs(k+1, tt+dis[pre][j], i);
v[j] = false;
}
}
}
int main(){
scanf("%d%d", &n, &m);
a[0] = 1;
for(int i=1; i<=5; i++) scanf("%d", &a[i]);
memset(h, -1, sizeof h);
for(int i=0; i<m; i++){
scanf("%d%d%d", &x, &y, &t);
add(x, y, t), add(y, x, t);
}
for(int i=0; i<=5; i++) h_dijkstra(i); //spfa(i); 被卡掉了
memset(v, false, sizeof v);
dfs(0, 0, 0);
cout<< ans<< endl;
return 0;
}