#include<cstdio>
#include<vector>
#include<set>

using namespace std;

#define minim(a,b) ((a<b)? a:b)
#define inf 999999999
#define kmax 15
#define nmax 10001
#define pi pair<int,int>
#define f first
#define s second
#define mp make_pair
#define pb push_back

int n,m,k,c[kmax];
int source[nmax],path[kmax][nmax];
vector<pi> g[nmax];
int pd[1<<kmax][kmax];
set<pi> q;
inline int bit(int x,int nr)
{ return(x&(1<<nr))!=0;}

void dijkstra(int sursa, int *sol)
{
	int i,vec;
	for(i=1;i<=n;++i)
		sol[i]=inf;
	sol[sursa]=0;
	q.clear();
	for(i=1;i<=n;i++)
		q.insert(mp(sol[i],i));
	for(i=1;i<n;++i)
	{
		pi top=*q.begin();
		q.erase(q.begin());
		int nod=top.s;
		if(sol[nod]<top.f) continue;
		for(size_t j=0;j<g[nod].size();++j)
			if(sol[vec=g[nod][j].f]>sol[nod]+g[nod][j].s)
			{
				sol[vec]=sol[nod]+g[nod][j].s;
				q.insert(mp(sol[vec],vec));
			}
	}
}

int main()
{
	int i,j,l,newcost;
	freopen("ubuntzei.in","r",stdin);
	freopen("ubuntzei.out","w",stdout);
	
	scanf("%d%d%d",&n,&m,&k);
	for(i=0;i<n;++i)
		scanf("%d",&c[i]);
	for(;m;--m)
	{
		scanf("%d%d%d",&i,&j,&k);
		g[i].pb(mp(j,k));
		g[j].pb(mp(i,k));
	}
	dijkstra(1,source);
	if(!k)
	{
		printf("%d\n",source[n]);
		return 0;
	}
	for(i=0;i<k;++i)
		dijkstra(c[i],path[i]);
	for(i=1;i<(1<<k);++i)
	{
		for(j=0;j<k;++j)
			if(i==(1<<j))
				break;
			if(j<k&&i==(1<<j))
			{
				pd[i][j]=source[c[j]];
				continue;
			}
			for(j=0;j<k;++j)
			{
				pd[i][j]=inf;
				if(bit(i,j))
					for(l=0;l<k;++l)
						if(l!=j&&bit(i,l))
						{
							newcost=pd[i-(1<<j)][l]+path[k][c[j]];
							pd[i][j]=minim(pd[i][j],newcost);
						}
			}
	}
	int bst=inf;
	for(i=0;i<k;++i)
		bst=minim(bst,pd[(1<<k)-1][i]+path[i][n]);
	printf("%d",bst);
	return 0;
}