$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$。