Autobus

문제

In a country there are $nn$ cities. The cities are connected by $mm$ bus routes, where the $ii$-th route starts in city $a_{i}a\_i$, ends in city $b_{i}b\_i$ and takes $t_{i}t\_i$ minutes.

Ema loves to travel, but doesn’t like transferring between buses. On her trip she wants to use at most $kk$ different bus routes.

Help her answer $qq$ questions of the form ‘What is the shortest travel time to get from city $c_{j}c\_j$ to city $d_{j}d\_j$ (using at most $kk$ different bus routes)?’.

입력

The first line contains two positive integers $nn$ and $mm$ (2 ≤ n ≤ 70, 1 ≤ m ≤ 10^6), the number of cities and the number of bus routes.

The $ii$-th of the next $mm$ lines contains positive integers $a_{i}a\_i$, $b_{i}b\_i$ and $t_{i}t\_i$ (1 ≤ a_i , b_i ≤ n, 1 ≤ t_i ≤ 10^6), the terminal cities and the travel time of the $ii$-th bus route.

The next line contains two positive integers $kk$ and $qq$ (1 ≤ k ≤ 10^9, 1 ≤ q ≤ n^2), the maximum number of used routes and the number of queries.

The $jj$-th of the next $qq$ lines contains positive integers $c_{j}c\_j$ and $d_{j}d\_j$ (1 ≤ c_j , d_j ≤ n), the cities from the $jj$-th query.

출력

Print $qq$ lines. In the $jj$-th line print the shortest travel time from the $jj$-th query, or -1 if there is no trip that satisfies the requirements.

힌트

Clarification of the examples:

The answer to the first query from each example is marked on the graph.

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
1 3
1 4
4 2
3 3

10
-1
0

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
2 3
1 4
4 2
3 3

6
4
0

4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
3 3
1 4
4 2
3 3

3
4
0