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.