Rebuilding Village Roads

Given a region with (N) villages numbered from (0) to (N-1) and (M) bidirectional roads with specified lengths, each village (i) is rebuilt and available on day (t_i) (if (t_i = 0) then the village is undamaged and available from the start).

There are (Q) queries; each query is represented as ((x, y, t)). For each query, if either village (x) or village (y) is not yet rebuilt by day (t), or if there is no path from (x) to (y) using only villages rebuilt by day (t), you should output (-1). Otherwise, output the shortest path distance from (x) to (y) using only the available villages.

inputFormat

The first line contains two integers (N) and (M).

Each of the next (M) lines contains three integers (u), (v), and (w) indicating a bidirectional road between villages (u) and (v) with length (w).

The following line contains (N) integers (t_0, t_1, \dots, t_{N-1}) where (t_i) is the day village (i) is rebuilt ((t_i = 0) means the village was not damaged).

The next line contains an integer (Q), the number of queries.

Each of the next (Q) lines contains three integers (x), (y), and (t) representing a query.

outputFormat

For each query, output a single integer representing the shortest path length from village (x) to village (y) on day (t) using only villages that have been rebuilt by that day. If the path does not exist or if either (x) or (y) is not available by day (t), output (-1).

sample

4 4
0 1 2
1 2 3
2 3 4
0 3 10
1 2 3 4
3
0 3 1
0 3 4
1 2 2

-1
9
-1