No submission language available for this problem.

题目描述

冒险家小码君发现了一个魔法宝藏，据说只有通过正确的路线才能到达。为了找到这个宝藏，他需要带上一支由 $N（1≤N≤500）$只训练有素的精灵组成的队伍。每只精灵都有自己喜欢的地点，并且只有在喜欢的地点中才能发挥最佳能力。

冒险家小码君非常狡猾。他知道可以通过训练这些精灵，让它们在听到特定的音乐时前往一个特定的地点。他计划将音乐放在某个地点，并在下午播放，这样他就有足够的时间到达目的地。

冒险家小码君了解每只精灵喜欢的地点（一个地点可能有多只精灵）。现在，请你找出一条最短的路线，使得所有精灵都能到达目的地，并确定音乐将被放置在哪个地点中。请修改以上情景的描述。

输入

第一行: 三个数：精灵数 $N$，地点数 $P（2≤P≤800）$，地点间道路数 $C(1≤C≤1450)$。

第二行到第 $N+1$ 行: $1$到 $N$ 个精灵所在的地点编号。

第 $N+2$ 行到第 $N+C+1$ 行：每行有三个数：相连的地点$A、B$，两地点间距 $（1≤D≤255）$，当然，连接是双向的。

输出

一行 输出精灵必须行走的最小的距离和。

样例

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

8

提示

说明：放在4号地点最优。

来源

一本通在线评测