[HNOI2014] 道路堵塞

题目背景

### 本题可能不存在正确解法,题解均已被 hack。

题目描述

A 国有 $N$ 座城市,依次标为 $1$ 到 $N$。同时,在这 $N$ 座城市间有 $M$ 条单向道路,每条道路的长度是一个正整数。现在,A 国交通部指定了一条从城市 $1$ 到城市 $N$ 的路径,并且保证这条路径的长度是所有从城市 $1$ 到城市 $N$ 的路径中最短的。不幸的是,因为从城市 $1$ 到城市 $N$ 旅行的人越来越多,这条由交通部指定的路径经常发生堵塞。现在 A 国想知道,这条路径中的任意一条道路无法通行时,由城市 $1$ 到 $N$ 的最短路径长度是多少。

输入输出格式

输入格式


输入文件第一行是三个用空格分开的正整数 $N$、$M$ 和 $L$,分别表示城市数目、单向道路数目和交通部指定的最短路径包含多少条道路。按下来 $M$ 行,每行三个用空格分开的整数 $a$、$b$ 和 $c$,表示存在一条由城市 $a$ 到城市 $b$ 的长度为 $c$ 的单向道路。这 $M$ 行的行号也是对应道路的编号,即其中第 $1$ 行对应的道路编号为 $1$,第 $2$ 行对应的道路编号为 $2$,......,第 $M$ 行对应的道路编号为 $M$。最后一行为 $L$ 个用空格分开的整数 $\operatorname{sp}(1),\ldots,\operatorname{sp}(L)$,依次表示从城市 $1$ 到城市 $N$ 的由交通部指定的最短路径上的道路的编号。

输出格式


输出文件包含 $L$ 行,每行为一个整数,第 $i$ 行($i = 1,2,\ldots,L$)的整数表示删去编号为 $\operatorname{sp}(i)$ 的道路后从城市 $1$ 到城市 $N$ 的最短路径长度。如果去掉后没有从城市 $1$ 到城市 $N$ 的路径,则输出 $-1$。

输入输出样例

输入样例 #1

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

输出样例 #1

6
6

说明

$100\%$ 的数据满足 $2 < N < 100000$,$1 < M < 200000$,$c \in [0, 10000] \cap \mathbb{Z}$。 数据已加强 By Vfleaking。 2023.4.8 添加两组 hack 数据。