子序列路径

题目描述

有编号为 $1, \dots, N$ 的 $N$ 个城镇,以及编号为 $1, \dots, M$ 的 $M$ 条道路。

每条道路都是有向的;第 $i$ 条道路 $(1 \leq i \leq M)$ 从城镇 $A_i$ 通向城镇 $B_i$,其长度为 $C_i$。

给定一个长度为 $K$、由 $1$ 到 $M$ 之间的整数组成的序列 $E = (E_1, \dots, E_K)$。如果一条从城镇 1 到城镇 N 的、使用道路的旅行方式满足以下条件,则称为好路径:

按使用顺序排列的道路编号所组成的序列是 $E$ 的一个子序列。

注:一个序列的子序列是指从原序列中删除 $0$ 个或多个元素,保持剩余元素顺序不变而得到的序列。

求好路径中所用道路长度之和的最小值。

如果不存在好路径,请报告这一事实。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• $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)$
• 输入中的所有值均为整数。