Dungeon

Time Limit : 2 sec, Memory Limit : 262144 KB

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

ai bi ci は 部屋 aibi を結ぶ通路の距離がciであることを表す。

入力は以下の制約を満たす
2 ≤ n ≤ 100,000
0 ≤ ai , bi < n
0 ≤ ci ≤ 100,000
n-1m ≤ 100,000
1 ≤ q ≤ 100,000
0 ≤ fsi , fgi ≤ 260

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

Source: Aizu Competitive Programming Camp 2012 , Day 2, Aizu-Wakamatsu, Japan, 2012-09-04
Problem Setter:  Tomoya Sakai, Kyugo Katsuta, Kazuki Yamamoto