Problem F : Dungeon (I)

あなたはとあるゲームの開発に携わっている。 そのゲームはランダムに生成されたダンジョンをプレイヤーが探索するというものである。

このゲームで生成されるダンジョンにはn 個の部屋が存在しており、0から n-1 までの番号が割り振られている。 部屋と部屋は通路で結ばれている。部屋と部屋を結ぶ通路は、m 本ある。 通路はどちらの方向へも進むことができる。 また、部屋と部屋の間には距離が設定されている。 生成されたダンジョンではいくつかの通路を経由して、ある部屋から他のすべての部屋へ行くことが可能である。 そして、プレイヤーがゲームを行う際に、0番の部屋がスタート地点、n-1 番の部屋がゴール地点として選ばれる。

ユーザーがダンジョンを探索する際に、手助けになるようなアイテムが入った宝箱を、どこかの部屋に設置したい。 その時に、スタート地点から遠すぎたり、ゴール地点から近すぎると意味がない。 そこで、スタートから距離 fs 以内で辿りつけて、ゴールに辿り着くために最短経路を通った場合に、少なくとも fg かかる部屋を宝箱を設置する候補としたい。

生成されたダンジョンと、q が与えられる。q 個のクエリーについて、宝箱を設置する場所の候補の数を数えて欲しい。

Input

入力は以下のフォーマットで与えられる。

n m
a1 b1 c1
.
.
.
am bm cm
q
fs1 fg1
.
.
.
fsq fgq

a_i b_i c_i は 部屋 a_i と b_i　を結ぶ通路の距離がc_iであることを表す。

入力は以下の制約を満たす
2 ≤ n ≤ 100,000
0 ≤ a_i , b_i < n
0 ≤ c_i ≤ 100,000
n-1 ≤ m ≤ 100,000
1 ≤ q ≤ 100,000
0 ≤ fs_i , fg_i ≤ 2⁶⁰

Output

各クエリーについて、答えの値を1行に出力せよ

Sample Input 1

4 4
0 1 3
1 3 4
0 2 2
2 3 1
4
0 0 
2 2
2 1
3 4

Sample Output 1

1
1
2
1