农夫$John$发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道$N(1\leqslant N\leqslant 500)$只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

农夫$John$很狡猾。像以前的$Pavlov$，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

农夫$John$知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）

第一行: 三个数：奶牛数$N$，牧场数$P(2\leqslant P\leqslant 800)$，牧场间道路数$C(1\leqslant C\leqslant 1450)$

第二行到第$N+1$行: $1$到$N$头奶牛所在的牧场号

第$N+2$行到第$N+C+1$行： 每行有三个数：相连的牧场$A,B$，两牧场间距离$D(1\leqslant D\leqslant 255)$，当然,连接是双向的

一行 输出奶牛必须行走的最小的距离和

输入

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

输出

8

枚举所有农场并对每个点都$SPFA$，求和取最小值

#include

#define Space putchar(' ')
#define Enter puts("")
#define MAXN 100010

using namespace std;

typedef long long ll;
typedef double Db;

inline ll Read()
{
ll Ans = 0;
char Ch = getchar() , Las = ' ';
while(!isdigit(Ch))
{
Las = Ch;
Ch = getchar();
}
while(isdigit(Ch))
{
Ans = (Ans << 3) + (Ans << 1) + Ch - '0';
Ch = getchar();
}
if(Las == '-')
Ans = -Ans;
return Ans;
}

inline void Write(ll x)
{
if(x < 0) { x = -x; putchar('-'); } if(x >= 10)
Write(x / 10);
putchar(x % 10 + '0');
}

struct Edge
{
int Next , To , Dis;
}E[MAXN];

int Dis[MAXN] , Head[MAXN] , Count;

inline void Add_Edge(int u , int v , int d)
{
E[++Count].Dis = d;
E[Count].To = v;
E[Count].Next = Head[u];
Head[u] = Count;
}

int n , p , c , Start;
int G[MAXN];
queue Q;
bool Visit[MAXN];

inline void SPFA()
{
memset(Visit , false , sizeof(Visit));
for(int i = 1; i <= p; i++) Dis[i] = MAXN; Dis[Start] = 0; Q.push(Start); Visit[Start] = true; while(!Q.empty()) { int u = Q.front(); Q.pop(); Visit[u] = false; for(int i = Head[u]; i; i = E[i].Next) { int v = E[i].To; if(Dis[v] > Dis[u] + E[i].Dis)
{
Dis[v] = Dis[u] + E[i].Dis;
if(!Visit[v])
{
Q.push(v);
Visit[v] = true;
}
}
}
}
}

int main()
{
n = Read() , p = Read() , c = Read();
for(int i = 1; i <= n; i++)
G[i] = Read();
for(int i = 1; i <= c; i++)
{
int u = Read() , v = Read() , d = Read();
Add_Edge(u , v , d);
Add_Edge(v , u , d);
}
int MIN = 999999999;
for(int i = 1; i <= p; i++)
{
Start = i;
SPFA();
int Ans = 0;
for(int j = 1; j <= n; j++)
Ans += Dis[G[j]];
MIN = min(MIN , Ans);
}
Write(MIN);
return 0;
}