AT_codequeen2025_final_g 全国ツアー

日本有 $N$ 座城市，这些城市之间通过 $M$ 条双向道路相连。每座城市从 $1$ 编号到 $N$，第 $i$ 条道路连接城市 $U_i$ 和城市 $V_i$，道路长度为 $C_i$ 千米。城市之间只能通过这些道路移动。 另外，在 $N$ 座城市中，有 $K$ 个城市设有演唱会会场。具体来说，对于 $k=1,2,\ldots,K$，城市 $A_k$ 设有演唱会会场。$K$ 满足 $K\geq4$，并保证城市 $1$ 和城市 $N$ 一定有演唱会会场。 人气偶像团体 Bit♡Beat 决定举办全国巡回演唱会。 此次巡回演唱会将在 $4$ 座不同的有演唱会会场的城市举行。其中，第一次演唱会必须在城市 $1$，最后一次必须在城市 $N$ 举办。 请你求出：从城市 $1$ 出发，在 $4$ 个城市（包括城市 $1$ 和城市 $N$）举办演唱会，最终到达城市 $N$，这一过程中所需的最小总移动距离。 注意，途中可以多次经过同一座城市。

输入以如下格式从标准输入读入。 > $N$ $M$ $K$ > $A_1$ $A_2$ $\ldots$ $A_K$ > $U_1$ $V_1$ $C_1$ > $U_2$ $V_2$ $C_2$ > ⋮ > $U_M$ $V_M$ $C_M$

请输出所需的最小总移动距离（千米数），仅输出整数，不输出单位。

### 样例解释 1 可以按如下方式完成在 $4$ 个城市的演唱会： - 在城市 $1$ 举办演唱会。 - 从城市 $1$ 移动到城市 $3$，行驶 $1$ 千米。 - 从城市 $3$ 移动到城市 $2$，行驶 $10$ 千米。 - 在城市 $2$ 举办演唱会。 - 从城市 $2$ 移动回城市 $3$，行驶 $10$ 千米。 - 从城市 $3$ 移动到城市 $4$，行驶 $100$ 千米。 - 在城市 $4$ 举办演唱会。 - 从城市 $4$ 移动到城市 $5$，行驶 $1000$ 千米。 - 在城市 $5$ 举办演唱会。 本例总移动距离为 $1121$ 千米。 不存在比 $1121$ 千米更短的路线，因此输出 $1121$。 ### 数据范围与约定 - $4 \le N \le 10^5$ - $N-1 \le M \le \min\left(2\times 10^5, \frac{N(N-1)}2 \right)$ - $1 \le U_i < V_i \le N$ - $1 \le C_i \le 10^9$ - 输入的图为简单连通图 - $4 \le K \le N$ - $1 = A_1 < A_2 < \ldots < A_K = N$ - 输入数据均为整数 由 ChatGPT 5 翻译