#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x7f7f7f7f;
int n,m,dis[7][50005],ct,head[50005],a,b,c,d,e,ans=inf;
bool vis[50005],viss[7];
struct inter{
	int id,walue;
}; 
inter stu[7];
struct nodee{
	int nxt,to,w;	
};
nodee mp[50005];
void add(int u,int v,int w){
	mp[++ct].nxt=head[u];
	head[u]=ct;
	mp[ct].to=v;
	mp[ct].w=w;
	
}
struct node{
	int value,i;
	friend bool operator<(node x,node y){
		return x.value>y.value;
	}
};
priority_queue <node> q;
int dijkstra(int s,int step){
//	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		dis[step][i]=inf;
	} 
	while(!q.empty()) q.pop();
	dis[step][s]=0;
	q.push(node{0,s});
	while(!q.empty()){
		node t=q.top();
		q.pop();
		if(vis[t.i]) continue;
		vis[t.i]=1;
		for(int i=head[t.i];i;i=mp[i].nxt){
			int f=mp[i].to;
			if(dis[step][f]>dis[step][t.i]+mp[i].w){
				dis[step][f]=dis[step][t.i]+mp[i].w;
				q.push(node{dis[step][f],f});
			}
		}
	}
} 
void dfs(int cnt,int k,int dist){
	if(cnt==6){
		ans=min(ans,dist);
		return;
	}
	for(int i=2;i<=6;i++){
		if(!viss[i]){
			viss[i]=1;
			dfs(cnt+1,stu[i].id,dist+dis[k][stu[i].walue]);
			viss[i]=0;
		} 	
	}
}
signed main(){
	cin>>n>>m;
	stu[1].id=1,stu[1].walue=1;
	for(int i=2;i<=6;i++){
		int y;
		cin>>y;
		stu[i].id=i,stu[i].walue=y;
	}
	memset(mp,0x7f,sizeof(mp));
	while(m--){
		int u,v,k;
		cin>>u>>v>>k;
		add(u,v,k);
		add(v,u,k);
	}
	for(int i=1;i<=6;i++){
		dijkstra(stu[i].walue,i);
	}         
//	for(int i=2;i<=6;i++){
		viss[1]=1;
		dfs(1,1,0);
		viss[1]=0;
//	}   
	cout<<ans;
	return 0;
}