题目描述

农夫John知道，要做出最甜的黄油，需要把糖放在一个牧场，让所有奶牛都能过来舔食。

已知有 $N$ 头奶牛，它们分别待在各自喜欢的牧场上（一个牧场可能有多头牛）。牧场之间通过 $C$ 条双向道路连接，每条道路有固定的长度。

请你帮农夫John找出一个最佳牧场来放糖，使得所有奶牛到达该牧场的路程总和最小。

输入格式

第一行：三个整数 $N, P, C$，分别表示奶牛数量、牧场数量和道路数量。 接下来 $N$ 行：每行一个整数，表示第 $i$ 头奶牛所在的牧场编号。 接下来 $C$ 行：每行三个整数 $A, B, D$，表示牧场 $A$ 和 $B$ 之间有一条双向道路，长度为 $D$。

输出格式

仅一行一个整数，表示所有奶牛必须行走的最小距离和。

输入输出样例

输入 #1

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

输出 #1

8

说明/提示

样例解释

将糖放在 4号牧场 最优。

• 2号牧场的奶牛到4号：距离为 3
• 3号牧场的奶牛到4号：距离为 5
• 4号牧场的奶牛到4号：距离为 0
• 总路程和：$3 + 5 + 0 = 8$

数据范围

• $1 \le N \le 500$
• $2 \le P \le 800$
• $1 \le C \le 1450$
• $1 \le D \le 255$