#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5+1e4+100,M=2*1e5+100;
int n,m,s;
int dis[N];
int z[N];
//lsqxx
int v[M];
int t[M];
int l[M];
int nt[M];
int p=0;
void add(int a,int b,int c){
	++p;
	v[p]=c;
	t[p]=b;
	nt[p]=l[a];
	l[a]=p;
}
//end
struct node{
	int p,dis;
	bool operator <(const node a)const{
		return a.dis<dis;
	}
};
priority_queue <node>q;
int vis[N];
void dij(){
	while(!q.empty()) q.pop();
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++) dis[i]=0x7fffffff;
	dis[s]=0;q.push({s,0});
	while(!q.empty()){
		node tt=q.top();
		q.pop();
		//if(vis[tt.p]) continue;
		vis[tt.p]=1;
		int now=tt.p;
		for(int j=l[now];j!=0;j=nt[j]){
			if(dis[now]+v[j]<dis[t[j]]){
				dis[t[j]]=dis[now]+v[j];
				if(!vis[t[j]]) q.push({t[j],dis[t[j]]});
			}
		}
	}
}
int vv[N];
int ss[N];
int d[N][N];
int ans=1e18;
void dfs(int deep,int cost){
	//cout<<deep<<endl;
	if(cost>=ans) return;
	if(deep==6){
		ans=min(ans,cost);
		return;
	}
	for(int i=1;i<=5;i++){
		if(vv[i]==0){
			vv[i]=1;
			ss[deep]=z[i];
			dfs(deep+1,cost+d[ss[deep-1]][z[i]]);
			vv[i]=0;
		}
	}
}
signed main(){
	s=1;
	cin>>n>>m;
	for(int i=1;i<=5;i++) cin>>z[i];
	for(int i=1;i<=m;i++){
		int t1,t2,t3;
		cin>>t1>>t2>>t3;
		add(t1,t2,t3);
		add(t2,t1,t3);
	}
	z[0]=1;
	for(int i=0;i<=5;i++){
		s=z[i];
		dij();
		for(int j=1;j<=n;j++) d[z[i]][j]=dis[j];
	}
	ss[0]=1;
	dfs(1,0);
	cout<<ans<<endl;
}

题目传送门：https://www.luogu.com.cn/problem/P5764 感谢！