#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
//N为点数，M为边数
const int N=50010,M=1e5*2+10,INF=0x3f3f3f3f;
//n为点数，m为边数，a为佳佳家和亲戚的车站编号，b为数组a的映射
int n,m,a[10],b[10]={0,1,2,3,4,5,6};
//邻接表建图
int h[N],e[M],ne[M],w[N],idx;
bool st[N];
//dist[i][j]表示从第i个亲戚所在的车站出发，到j号车站的最短路
//ans为答案
int dist[10][N],ans=INF;
//邻接表建图
void add(int a,int b,int c)
{
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
//dijkstra求第id个亲戚所在的车站为源点到其他点的最短路
//start为第id个亲戚所在的车站的编号
void dij(int id,int start)
{
    memset(st,0,sizeof st);
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,start});
    dist[id][start]=0;
    while(q.size())
    {
        PII t=q.top();
        q.pop();
        int d=t.x,v=t.y;
        if(st[v]) continue;
        st[v]=true;
        for(int i=h[v];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[id][j]>dist[id][v]+w[i])
            {
                dist[id][j]=dist[id][v]+w[i];
                q.push({dist[id][j],j});
            }
        }
    }
}
int main()
{
    memset(dist,0x3f,sizeof dist);
    memset(w,0x3f,sizeof w);
    memset(h,-1,sizeof h);
    cin>>n>>m;
    //佳佳家所在的车站编号是1，再依次输入其他亲戚所在的车站编号
    a[1]=1;
    for(int i=2;i<=6;i++) cin>>a[i];
    //建图
    while(m--)
    {
        int x,y,t;
        cin>>x>>y>>t;
        add(x,y,t);add(y,x,t);
    }
    //依次求最短路
    for(int i=1;i<=6;i++)
        dij(i,a[i]);
    //循环求最小值
    do
    {
        int time=0;
        time+=dist[b[1]][a[b[2]]];
        for(int i=2;i<=5;i++) time+=dist[b[i]][a[b[i+1]]];
        ans=min(ans,time);
    }while(next_permutation(b+2,b+6+1));
    
    cout<<ans;
    return 0;
}