{"raw_statement":[{"iden":"statement","content":"在一个国家里有 $n$ 座城市。这些城市由 $m$ 条公交线路连接，其中第 $i$ 条线路从城市 $a_i$ 出发，到 $b_i$ 停止，路程中耗时 $t_i$ 分钟。\n\nEma 喜欢旅行，但她并不喜欢在公交线路之间换乘。在旅行过程中，她希望**最多**只需坐 $k$ 个不同的公交线路。\n\nEma 想知道，从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间是多少（最多坐 $k$ 个不同的公交线路）。"},{"iden":"input","content":"第一行包含两个整数 $n,m$，分别表示城市的数量和公交车线路的数量。\n\n接下来 $m$ 行，第 $i+1$ 包含三个整数 $a_i,b_i,t_i$，分别表示第 $i$ 条公交车线路的起点、终点和从起点到终点所需的时间。\n\n接下来一行包含两个整数 $k,q$，最大坐的不同公交线路的个数和问题题的个数。\n\n接下来 $q$ 行，第 $m+j+3$ 行包含两个整数 $c_j,d_j$，表示询问从城市 $c_j$ 到城市 $d_j$ 的最短旅行时间。"},{"iden":"output","content":"输出包含 $q$ 行，第 $i$ 行包含一个整数，表示从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间。"},{"iden":"note","content":"**【样例解释】**\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/kxv8k07a.png)\n\n每个样例中的答案都已经标记在图中。\n\n**【数据规模与约定】**\n\n**本题采用子任务捆绑测试。**\n\n- Subtask 1（15 pts）：$k ≤ n ≤ 7$。\n- Subtask 2（15 pts）：$k ≤ 3$。\n- Subtask 3（25 pts）：$k ≤ n$。\n- Subtask 4（15 pts）：没有额外限制。\n\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$。\n\n**【提示与说明】**\n\n**本题分值按 COCI 原题设置，满分 $70$。**\n\n**题目译自 [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T2  Autobus。** "}],"translated_statement":null,"sample_group":[["4 7\n1 2 1\n1 4 10\n2 3 1\n2 4 5\n3 2 2\n3 4 1\n4 3 2\n1 3\n1 4\n4 2\n3 3\n","10\n-1\n0"],["4 7\n1 2 1\n1 4 10\n2 3 1\n2 4 5\n3 2 2\n3 4 1\n4 3 2\n2 3\n1 4\n4 2\n3 3","6\n4\n0\n"],["4 7\n1 2 1\n1 4 10\n2 3 1\n2 4 5\n3 2 2\n3 4 1\n4 3 2\n3 3\n1 4\n4 2\n3 3","3\n4\n0\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}