A. 吝啬的拒绝

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

拒绝家里养了好多的牛牛，

现在把饲养槽放在一片牧场上，因为他知道会有 $N$ 只牛牛过来吃饲料，

但是，拒绝很狡猾，他不想多弄点饲料槽，只想弄一个饲料槽在其中的一个牧场里，让所有的牛过来吃。

拒绝知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。

给出各头牛在的牧场和牧场间的路线，你需要告诉他牛牛们最短需要走多少路。

数据保证至少存在一个牧场和所有牛所在的牧场连通。

第一行: 三个数：奶牛数 $N$ ，牧场数 $P$ ，牧场间道路数 $C$ 。

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

第 $N+2$ 行到第 $N+C+1$ 行：每行有三个数：相连的牧场 $A$ 、 $B$ ，两牧场间距 $D$ 。（每条道路都是双向的）

共一行，输出奶牛必须行走的最小的距离。

该样例中，把饲料槽放在 $4$ 号牧场牛牛们走的总距离最短。

$1≤N≤500,2≤P≤800,1≤C≤1450,1≤D≤255$