Minimize Walking Distance in Magic City

In the magical city where rain is frequent, the urban area is modeled as an undirected connected graph with $n$ nodes and $m$ edges. Each edge is described by its length $l$ and altitude $a$. Due to heavy seasonal rains, roads accumulate water. The drainage system makes sure that the flooded roads are exactly those with the lowest altitudes: when the water level is set to $p$, every road whose altitude $\leq p$ is flooded. Cars cannot travel through flooded roads, but pedestrians can go along any road.\n\nYazid, a local resident and competitor, has his home at node $1$. Over $Q$ days, on each day he provides a starting node $v$ and a water level $p$. Starting at $v$, he is provided with a car which can drive only on non-flooded (safe) edges (i.e. edges with altitude $> p$). At any node he may choose to abandon the car and complete his journey on foot (which can use any road). However, once he leaves the car, he must continue walking, and the car he left behind will not be available later (cars are reset on each day).\n\nHelp Yazid minimize the total walking distance—the sum of the lengths of the edges he must walk on—on his journey to his home. Equivalently, let $d(u)$ be the shortest walking distance (using any roads) from node $u$ to node $1$. On a given day with starting node $v$ and water level $p$, let $S$ be the set of nodes reachable from $v$ using roads with altitude $> p$ (i.e. via car). The answer is ( \min_{u \in S} d(u) ).\n\nNote that the graph is connected (by all roads) and the car is available fresh each day.

inputFormat

The first line contains two integers $n$ and $m$, representing the number of nodes and edges.\n\nThe next $m$ lines each contain four integers $u$, $v$, $l$, and $a$, describing an edge between nodes $u$ and $v$ with length $l$ and altitude $a$.\n\nThe following line contains an integer $Q$, the number of queries.\n\nEach of the next $Q$ lines contains two integers $v$ and $p$, which are the starting node and the water level for that day.

outputFormat

For each query, output a single integer representing the minimum total walking distance from the starting node $v$ (given the water level $p$) to home at node $1$.

sample

4 4
1 2 3 5
2 3 2 3
3 4 4 6
2 4 1 2
2
3 4
4 2

4
0