Problem Description

In a country, there are $n$ cities. These cities are connected by $m$ bus routes. The $i$-th route starts from city $a_i$ and stops at city $b_i$, and it takes $t_i$ minutes along the way.

Ema likes traveling, but she does not like transferring between bus routes. During a trip, she wants to take at most $k$ different bus routes.

Ema wants to know the shortest travel time from city $c_i$ to city $d_i$ (using at most $k$ different bus routes).

Input Format

The first line contains two integers $n, m$, representing the number of cities and the number of bus routes.

The next $m$ lines describe the routes. The $(i+1)$-th line contains three integers $a_i, b_i, t_i$, representing the start city, the end city, and the time needed from the start to the end for the $i$-th bus route.

The next line contains two integers $k, q$, representing the maximum number of different bus routes that can be taken, and the number of queries.

The next $q$ lines describe the queries. The $(m+j+3)$-th line contains two integers $c_j, d_j$, asking for the shortest travel time from city $c_j$ to city $d_j$.

Output Format

Output $q$ lines. The $i$-th line contains one integer, the shortest travel time from city $c_i$ to city $d_i$.

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

Hint

Sample Explanation.

In each sample, the answers have been marked in the figure.

Constraints.

This problem uses bundled subtasks.

• Subtask 1 (15 pts): $k \le n \le 7$.
• Subtask 2 (15 pts): $k \le 3$.
• Subtask 3 (25 pts): $k \le n$.
• Subtask 4 (15 pts): No additional constraints.

For $100\%$ of the testdata, $2 \le n \le 70$, $1 \le m, t_i \le 10^6$, $1 \le a_i, b_i, c_j, d_j \le n$, $1 \le k \le 10^9$, and $1 \le q \le n^2$.

Hints and Notes.

The score setting follows the original COCI problem, with a full score of $70$.

Translated from COCI2021-2022 CONTEST #4 T2 Autobus.

Translated by ChatGPT 5