Detour under Road Blockage

A country has \(N\) cities labeled from \(1\) to \(N\) and \(M\) directed roads. Each road has a positive integer length. The Ministry of Transportation has designated a route from city \(1\) to city \(N\) which is guaranteed to be one of the shortest routes from \(1\) to \(N\). However, due to heavy traffic, any single road on this designated route might become blocked. Your task is to determine, for each road on the designated route, what the shortest path length from city \(1\) to city \(N\) would be if that particular road were blocked. If no alternate path exists, print \(-1\).

Note: The designated route is provided as a sequence of cities. For each consecutive pair \(P_i\) and \(P_{i+1}\) in the sequence, there exists an edge from \(P_i\) to \(P_{i+1}\) with a given weight, and the sum of these weights equals the shortest distance from city \(1\) to city \(N\) in the original graph.

Input Format: The first line contains two integers \(N\) and \(M\). The following \(M\) lines each contain three integers \(u\), \(v\), and \(w\), representing a directed road from city \(u\) to city \(v\) with weight \(w\). The next line contains an integer \(K\), the number of cities in the designated route. The last line contains \(K\) integers representing the designated route.

Output Format: Print \(K-1\) lines. The \(i\)-th line should contain a single integer representing the length of the shortest path from city \(1\) to city \(N\) when the \(i\)-th road of the designated route (from \(P_i\) to \(P_{i+1}\)) is blocked. If there is no path, print \(-1\).

inputFormat

The input begins with two integers \(N\) and \(M\) separated by a space.

Then \(M\) lines follow, each containing three integers \(u\), \(v\), and \(w\), representing a directed edge from \(u\) to \(v\) with weight \(w\).

The next line contains an integer \(K\), representing the number of cities on the designated route.

The last line contains \(K\) integers, which are the labels of the cities in the designated route in order. It is guaranteed that the first city is \(1\) and the last is \(N\), and that the sum of the weights on the designated route equals the shortest path from \(1\) to \(N\).

outputFormat

Output \(K-1\) lines. Each line contains one integer: the shortest path length from city \(1\) to city \(N\) when the corresponding road on the designated route is blocked. If no path exists, print \(-1\) for that case.

sample

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

3
3