Bytetown 有 $n$ 个交叉路口，由 $m$ 条单向街道连接。这些交叉路口编号为 $1, 2, \dots, n$。小 Q 非常喜欢运动步行，他计划进行 $q$ 天的步行。在第 $i$ 天，小 Q 计划从第 $s_i$ 个交叉路口出发，沿街道移动至少 $k_i$ 次，最后到达第 $t_i$ 个交叉路口。注意 $k_i$ 是要求的移动次数，而不是街道数：允许多次经过同一条街道。

小 Q 的智能手机会记录他的步行路线。小 Q 比起保持健康，更关心统计数据。因此，他希望最小化每天的总步行长度。请编写一个程序来帮助他找到最佳路线。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 50, 1 \le m \le 10\,000$)，分别表示交叉路口和单向街道的数量。

接下来的 $m$ 行，每行包含三个整数 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10\,000$)，表示一条从交叉路口 $u_i$ 到 $v_i$、长度为 $w_i$ 的单向街道。

下一行包含一个整数 $q$ ($1 \le q \le 100\,000$)，表示天数。

接下来的 $q$ 行，每行包含三个整数 $s_i, t_i, k_i$ ($1 \le s_i, t_i \le n, 1 \le k_i \le 10\,000$)，描述当天的步行计划。

输出格式

对于每个步行计划，输出一行，包含一个整数：最小总步行长度。如果无解，请输出 “-1”。

样例

样例输入 1

2
3 3
1 2 1
2 3 10
3 1 100
3
1 1 1
1 2 1
1 3 1
2 1
1 2 1
1
2 1 1

样例输出 1

111
1
11
-1