题目描述

农场主老周研究出了熬出顶级糖浆的秘方：只要让奶牛们围着一口糖锅打转，糖浆就会格外香甜。

牧场里共有 $P$ 片草场，草场之间由 $C$ 条双向小路相连。老周的 $N$ 头奶牛各自常年待在自己钟爱的草场上（同一片草场可能住着多头牛）。老周打算选一片草场支起糖锅，再摇铃把所有奶牛召集过来。他希望你帮他算出：把糖锅放在哪片草场，所有奶牛走过的路程之和最小？输出这个最小的路程和即可。

输入格式

第一行包含三个整数 $N,P,C$，分别表示奶牛数、草场数和草场间小路数。

第二行到第 $N+1$ 行，每行一个整数，其中第 $i$ 行的整数表示第 $i-1$ 头奶牛所在的草场编号。

第 $N+2$ 行到第 $N+C+1$ 行，每行包含三个整数 $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 A,B \le P$，$1 \le C \le 1450$，$1 \le D \le 255$。

样例解释

把糖锅放在 $4$ 号草场时路程之和最小，为 $8$。