Country A has $N$ cities, labeled $1$ to $N$. There are $M$ one-way roads between these $N$ cities, and the length of each road is a positive integer. The Ministry of Transport of Country A has designated a path from city $1$ to city $N$, and it is guaranteed that the length of this path is the shortest among all paths from city $1$ to city $N$.

Unfortunately, as the number of people traveling from city $1$ to city $N$ increases, this designated path often becomes congested. Country A now wants to know the length of the shortest path from city $1$ to city $N$ if any single road on this designated path becomes impassable.

Input

The first line contains three space-separated positive integers $N$, $M$, and $L$, representing the number of cities, the number of one-way roads, and the number of roads in the shortest path designated by the Ministry of Transport, respectively.

The next $M$ lines each contain three space-separated integers $a$, $b$, and $c$, representing a one-way road from city $a$ to city $b$ with length $c$. The line number of these $M$ lines also serves as the road's identifier; the first line corresponds to road $1$, the second line to road $2$, ..., and the $M$-th line to road $M$.

The last line contains $L$ space-separated integers $sp(1), \dots, sp(L)$, which represent the identifiers of the roads on the shortest path designated by the Ministry of Transport from city $1$ to city $N$, in order.

Output

The output contains $L$ lines, each containing a single integer. The integer on the $i$-th line ($i=1, 2, \dots, L$) represents the length of the shortest path from city $1$ to city $N$ after removing the road with identifier $sp(i)$. If there is no path from city $1$ to city $N$ after the removal, output -1.

Constraints

• $10\%$ of the data satisfies $N \le 10$.
• $40\%$ of the data satisfies $N \le 2000$ and $1 \le M \le 10000$.
• $100\%$ of the data satisfies $2 \le N \le 100000$ and $1 \le M \le 200000$.
• All road lengths are greater than $0$ and less than $10000$.
• The input path is guaranteed to be a valid shortest path from city $1$ to city $N$.

Examples

Input 1

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

Output 1

-1
7
7

Input 2

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

Output 2

-1