infoarena

#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
#define fin "zmeu.in"
#define fout "zmeu.out"
#define nMax 1001
#define Inf 200001

using namespace std;

int A[nMax][nMax];
int D[6][nMax];
int s[nMax];
int Porti[6];

int n, m, p;
int F[6], FF;
int I[nMax];

void citeste()
{
	fstream in(fin, ios::in);
	in>>n>>m>>p>>FF;
	for(int i=1;i<=5;i++) in>>F[i];
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j) A[i][j] = 0; else A[i][j] = Inf;
	for(int i=1;i<=m;i++)
	{
		int x, y, c;
		in>>x>>y>>c;
		A[x][y] = A[y][x] = c;
	}
	for(int i=1;i<=p;i++)
		in>>I[i];
	in.close();
}

void Dijkstra(int nod, int f)
{
	memset(s, 0, sizeof(s));
	s[nod] = 1;
	
	for(int i=1;i<=n;i++) 
		D[f][i] = A[nod][i];
	
	for(int i=1;i<n;i++)
	{
		int min = Inf, jmin;
		for(int j=1;j<=n;j++)
			if(!s[j]) if(min>D[f][j])
			{
				min = D[f][j];
				jmin = j;
			}
			
		s[jmin] = 1;
		for(int j=1;j<=n;j++)
			if(!s[j]) if(D[f][j] > min + A[jmin][j])
				D[f][j] = min + A[jmin][j];
	}
}

void solve()
{
	for(int i=1;i<=5;i++)
		Dijkstra(F[i], i);
	
	vector<int> sol;
	vector<int>::iterator it;
	
	for(int i=1;i<=5;i++) sol.push_back(i);
	
	for(int i=1;i<=5;i++)
	{
		int min = Inf;
		for(int j=1;j<=p;j++)
			if(min > D[i][I[j]]) min = D[i][I[j]];
		Porti[i] = min;
	}
	
	int Dist = Inf;
	do
	{
		int d;
		d = D[sol[0]][FF] + D[sol[1]][F[sol[0]]] + D[sol[2]][F[sol[1]]] + D[sol[3]][F[sol[2]]] + D[sol[4]][F[sol[3]]];
		d += Porti[sol[4]];
		
		if(d < Dist) Dist = d;
	}while(next_permutation(sol.begin(), sol.end()));
	
	fstream out(fout, ios::out);
	out<<Dist<<endl;
	out.close();
}

void tipar()
{
	for(int i=1;i<=5;i++)
		cout<<Porti[i]<<" ";
	cout<<endl;
}

int main(void)
{
	citeste();
	solve();
	//tipar();
	return 0;
}