思路：最短路-堆优化Dijkstra

本题是一道堆优化的 Dijkstra 模板题。

每次从 $1$ 号点到达 $x$ 号点后，需要从 $x$ 号点再返回 $1$ 号点。 有 $q(1\leq q < 10^5)$ 次询问，所以单次时间复杂度不能超过 $O(\log n)$

从 $1$ 号点到达 $x$ 号点的最短距离，必然也是从 $x$ 号点到达 $1$ 号点的最短距离。所以相当于到达每个点再返回的总距离就是从 $1$ 号点到达给定 $q$ 个点的总距离乘 $2$ 。

这就是一个单源最短路径问题，由于数据规模是 $1\leq n,m < 10^5$ ，所以需要堆优化的 Dijkstra 来解决。

题目描述

小红参加了一个闯关游戏，游戏地图是一个迷宫，一共有 $n$ 个地点，并且这 $n$ 个地点通过 $m$ 条路进行联通。

由于游戏规则要求，小红每次要从起点( $1$ 号节点)取一面旗帜，并放到官方要求的地点，然后返回起点，直到将所有旗送完。

小红一共要送 $q$ 次旗，他想知道，他需要走的最短路程是多少？

输入描述

第一行输入三个整数 $n,m,q(1 \leq n,m,q \leq 10^5)$ ，分别表示地点数、路径数和需要送达旗帜的地点数。

接下来 $m$ 行，每行输入三个整数 $u,v(1 \leq u,v\leq n,u≠v),w(1 \leq w \leq 10^4)$ ，表示地点 $u$ 和地点 $v$ 之间有一条长度为 $w$ 的道路。

最后一行输入 $q$ 个整数，表示需要送达旗帜的 $q$ 个地点。

输出描述

一个整数表示答案

示例1

输入

4 3 3
1 2 1
2 3 2
3 4 3
2 3 4

输出

20

说明

从 1号点到 2 号点再回来，路程距离为 2。 再从 1号点到 3 号点再回来，路程距离为 6。 最后从 1 号点到 4 号点再回来，路程距离为 12。