题目描述

有 $N$ 头奶牛和 $P$ 个牧场，一座牧场可能有多头奶牛。牧场之间由双向道路连接。

农夫想选择一座牧场放糖，让所有奶牛沿最短路线到这里集合。求所有奶牛行走距离之和的最小值。

输入格式

第一行三个整数 $N,P,C$，分别表示奶牛数、牧场数和道路数。

接下来 $N$ 行，每行一个整数，表示一头奶牛所在的牧场。

接下来 $C$ 行，每行三个整数 $A,B,D$，表示两个牧场之间有一条长度为 $D$ 的双向道路。

输出格式

输出最小的距离总和。

样例

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

8

数据范围

$1\le N\le500$，$2\le P\le800$，$1\le C\le1450$，$1\le A,B\le P$，$1\le D\le255$。保证图连通。