题目描述

$n$ 个小镇，$m$ 条双向道路。第 $i$ 条道路从 $a_i$ 通向 $b_i$，长度为 $c_i$。车的油箱容量为 $L$，当行驶到一个镇上时可以选择加满油或者什么都不做。行驶单位长度的距离消耗一单位的油。

现在回答 $Q$ 个问题：

• 油箱现在为满，从 $s_i$ 到 $t_i$，最少需要加油多少次，或者输出无解。

$2\le n\le 300$，$0\le m\le n(n - 1)/2$，无重边，无自环。$1\le c_i, L\le 10^9$。

输入格式

第一行两个数 $n,m$。

往后 $M$ 行，每行三个数，分别为道路的两端和长度。

输出格式

总共 $Q$ 行，每行一个数，为最少加油的次数。若无解输出 $-1$。

3 2 5
1 2 3
2 3 3
2
3 2
1 3

0
1

4 0 1
1
2 1

-1

5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
20
2 1
3 1
4 1
5 1
1 2
3 2
4 2
5 2
1 3
2 3
4 3
5 3
1 4
2 4
3 4
5 4
1 5
2 5
3 5
4 5

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0