题目描述

农夫 John 知道 $N$ 只奶牛分别在各自喜欢的牧场。现在要选择一个牧场放糖，使所有奶牛走到这个牧场的距离总和最小。

给出奶牛所在牧场和牧场之间的双向道路，请求出所有奶牛必须行走的最小距离和。

输入格式

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

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

接下来 $C$ 行，每行输入三个整数 $A,B,D$，表示牧场 $A$ 和牧场 $B$ 之间有一条距离为 $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 \le 500$，$2 \le P \le 800$，$1 \le C \le 1450$，$1 \le D \le 255$。道路均为双向道路。