24470번 - Autobus 서브태스크다국어

In a country there are $n$ cities. The cities are connected by $m$ bus routes, where the $i$-th route starts in city $a_i$, ends in city $b_i$ and takes $t_i$ minutes.

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

Help her answer $q$ questions of the form ‘What is the shortest travel time to get from city $c_j$ to city $d_j$ (using at most $k$ different bus routes)?’.

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

The $i$-th of the next $m$ lines contains positive integers $a_i$, $b_i$ and $t_i$ ($1 ≤ a_i , b_i ≤ n$, $1 ≤ t_i ≤ 10^6$), the terminal cities and the travel time of the $i$-th bus route.

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

The $j$-th of the next $q$ lines contains positive integers $c_j$ and $d_j$ ($1 ≤ c_j , d_j ≤ n$), the cities from the $j$-th query.

Print $q$ lines. In the $j$-th line print the shortest travel time from the $j$-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.