当前没有测试数据。

E - 子序列路径

得分：500分

问题描述

有$N$个编号为$1, \dots, N$的城镇和$M$条编号为$1, \dots, M$的道路。
每条道路都是有方向的；道路$i$ $(1 \leq i \leq M)$把你从城镇$A_i$带到城镇$B_i$。道路$i$的长度为$C_i$。

给定一个长度为$K$的序列$E = (E_1, \dots, E_K)$，其中的元素是介于$1$和$M$之间的整数。如果从城镇$1$到城镇$N$的旅行方式是一条好路径，那么这条路径上使用的道路的编号序列是$E$的一个子序列。

注意一个序列的子序列是通过从原始序列中删除$0$个或多个元素，并将剩余的元素按照原来的顺序连接而得到的。

找到使用好路径的道路长度之和的最小值。
如果没有好路径，报告这个事实。

约束

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M, K \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N, A_i \neq B_i \, (1 \leq i \leq M)$
• $1 \leq C_i \leq 10^9 \, (1 \leq i \leq M)$
• $1 \leq E_i \leq M \, (1 \leq i \leq K)$
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出输入：

$N$ $M$ $K$

$A_1$ $B_1$ $C_1$

$\vdots$

$A_M$ $B_M$ $C_M$

$E_1$ $\ldots$ $E_K$

输出

找到使用好路径的道路长度之和的最小值。
如果没有好路径，输出-1。

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

4

有两种可能的好路径如下：

• 使用道路$4$。在这种情况下，使用道路的长度之和为$5$。
• 按照顺序使用道路$1$和$2$。在这种情况下，使用道路的长度之和为$2 + 2 = 4$。

因此，所需的最小值为$4$。

3 2 3
1 2 1
2 3 1
2 1 1

-1

没有好路径。

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

14