(0).(0) 999ms

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4+10, M = 2e5+10;
struct Edge{
    int to,nxt,w;
}e[M];
struct node{
    int to,w;
    bool operator<(const node &b)const
    {
        return w > b.w;
    }
};
int tot,h[N],dis[6][N],in[N],vis[N],ans = 0x3f3f3f3f;
vector<int> adds;
int n,m;
void add(int from,int to,int w)
{
    e[tot].to = to, e[tot].w = w, e[tot].nxt = h[from];
    h[from] = tot ++ ;
}
int dij(int pos)
{
    memset(in,0,sizeof in);
    int s = adds[pos];
    priority_queue<node> q;
    q.push({s,0}); dis[pos][s] = 0;
    while(q.size())
    {
        int fa = q.top().to; q.pop();
        if(in[fa]) continue;
        in[fa] = 1;
        for(int i = h[fa]; ~i; i = e[i].nxt)
        {
            int to = e[i].to;
            if(dis[pos][to] > dis[pos][fa] + e[i].w)
            {
                dis[pos][to] = dis[pos][fa] + e[i].w;
                q.push({to,dis[pos][to]});

            }
        }
    }
}
void dfs(int cnt,int u,int distance)
{
    if(cnt == 5)
    {
        ans = min(ans,distance);
        return;
    }
    for(int i = 1; i < 6; ++i)
    {
        if(vis[i]) continue;
        vis[i] = 1;
        dfs(cnt+1,i,distance + dis[u][adds[i]]);
        vis[i] = 0;
    }
}
int main()
{
    memset(h, -1, sizeof h); tot = 0;
    cin >> n >> m;
    adds.push_back(1);
    for(int i = 0,x; i < 5; ++i)
    {
        cin >> x;
        adds.push_back(x);
    }

    for(int i = 0, a, b, c; i < m; ++i)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c); add(b,a,c);
    }
    memset(dis, 0x3f, sizeof dis);
    for(int i = 0; i < 6; ++i)dij(i);
    dfs(0,0,0);
    cout << ans;
    return 0;
}