#include<iostream>
#include<cmath>
#define MAXN 99999999;
struct minn
{
	int distanc,type;
}; 
int n,p,c,co,cow[10000000],dis[10000000],data[810][810],x,y,dist;
using namespace std;
int main()
{
	cin>>n>>p>>c;
	minn aa;
	aa.distanc=9999999;aa.type=0;
	for(int i=1;i<=n;i++)
	{
		cin>>co;
		cow[co]++;
	}
	for(int i=1;i<=p;i++)
	{
		for(int j=1;j<=p;j++)
		{
			data[i][j]=MAXN;
			if(i==j) data[i][j]=0;
		}
	}
	for(int i=1;i<=c;i++)
	{
		cin>>x>>y>>dist;
		data[x][y]=dist; 
	}
	for(int u=1;u<=p;u++)
	{
		for(int i=1;i<=c;i++)
		{
			for(int j=1;j<=c;j++)
			{
				data[j][i]=data[i][j]=min(data[i][j],data[i][u]+data[u][j]);
			}
		}
	}
	for(int i=1;i<=p;i++)
	{
		for(int j=1;j<=p;j++)
		{
			dis[i]+=data[i][j]*(++cow[j]);
		}
	}
	for(int i=1;i<=p;i++)
	{
		if(dis[i]<=aa.distanc)
		{
			aa.distanc=dis[i];aa.type=i;
		}
	}
	cout<<aa.distanc;
}