Byteotia 基础设施部决定开发一个计算机程序，用于快速查找任意两个城镇之间的路径长度。如果 Byteotia 的居民总是想找最短路径，那倒不足为奇。然而，他们有时想知道第 $k$ 短的路径。此外，路径中可能存在环，即路径可以经过重复的城镇。

如果两个城镇之间有 4 条路径，其长度分别为 2、4、4 和 5，那么最短路径的长度为 2，第二短为 4，第三短为 4，第四短为 5。

任务

编写一个程序，完成以下功能：

• 从标准输入读取 Byteotia 道路网络的描述以及关于路径长度的查询。
• 计算并向标准输出写入查询的答案。

输入格式

标准输入的第一行包含两个正整数 $n$ 和 $m$，由单个空格分隔，$1 \le n \le 100$，$0 \le m \le n^2-n$。它们分别代表 Byteotia 的城镇数量和连接城镇的道路数量。城镇编号从 $1$ 到 $n$。

接下来的 $m$ 行，每行包含三个由空格分隔的整数：$a$、$b$ 和 $l$，$a \ne b$，$1 \le l \le 500$。每个三元组描述了一条从城镇 $a$ 到 $b$ 的单向道路，长度为 $l$。对于任意两个城镇，至多存在一条从 $a$ 到 $b$ 的道路。

下一行包含一个整数 $q$，$1 \le q \le 10\,000$，表示查询的数量。接下来的 $q$ 行包含查询，每行一个。每个查询由三个由空格分隔的整数组成：$c$、$d$ 和 $k$，$1 \le k \le 100$。该查询询问从城镇 $c$ 到城镇 $d$ 的第 $k$ 短路径的长度。

输出格式

程序应向标准输出写入查询的答案，每行一个。第 $i$ 行应写入第 $i$ 个查询的答案：一个整数，表示所求路径的长度；如果该路径不存在，则输出 -1。

样例

输入 1

5 5
1 2 3
2 3 2
3 2 1
1 3 10
1 4 1
8
1 3 1
1 3 2
1 3 3
1 4 2
2 5 1
2 2 1
2 2 2
1 1 2

输出 1

5
8
10
-1
-1
3
6
-1