You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

换乘

题目描述

在一个国家里有 $n$ 座城市。这些城市由 $m$ 条公交线路连接，其中第 $i$ 条线路从城市 $a_i$ 出发，到 $b_i$ 停止，路程中耗时 $t_i$ 分钟。

小明喜欢旅行，但她并不喜欢在公交线路之间换乘。在旅行过程中，她希望最多只需坐 $k$ 个不同的公交线路。因此她想知道，从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间是多少（最多坐 $k$ 个不同的公交线路）。

输入格式

第一行包含两个整数 $n,m$，分别表示城市的数量和公交车线路的数量。

接下来 $m$ 行，第 $i+1$ 包含三个整数 $a_i,b_i,t_i$，分别表示第 $i$ 条公交车线路的起点、终点和从起点到终点所需的时间。

接下来一行包含两个整数 $k,q$，表示最大坐的不同公交线路的个数和问题的个数。

接下来 $q$ 行，第 $m+j+3$ 行包含两个整数 $c_j,d_j$，表示询问从城市 $c_j$ 到城市 $d_j$ 的最短旅行时间。

输出格式

输出包含 $q$ 行，第 $i$ 行包含一个整数，表示从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间。如果从 $c_i$ 无法到达 $d_i$ 则输出 $-1$。

样例 #1

样例输入 #1

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

样例输出 #1

10
-1
0

样例 #2

样例输入 #2

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

样例输出 #2

6
4
0

样例 #3

样例输入 #3

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

3
4
0

提示

数据范围

对$10\%$的数据，$k ≤ n ≤ 7$。

对另外$20\%$的数据，$k ≤ 3$。

对$50\%$的数据，$k ≤ n$。

对$100\%$的数据，$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\le10^9,1\le q \le n^2$。