Counting Shortest Paths in a Road Network

Robot police have obtained a map which records the length of every road in the district. Since criminals always choose the shortest path to minimize the risk of being caught, the police are interested in determining the number of possible shortest paths between any two locations. In other words, given a road network, for a query between two nodes \(s\) and \(t\), you are to calculate how many routes exist such that the total path length is minimized.

The road network is given as an undirected weighted graph. For each query, if there is no available path from \(s\) to \(t\), output 0.

Note: All formulas are in \(\LaTeX\) format. For instance, the shortest distance from \(s\) to \(t\) is denoted by \(d(s,t)\), and the count of shortest paths by \(\text{cnt}(s,t)\).

inputFormat

The first line of input contains two integers \(n\) and \(m\) \( (1 \leq n \leq 10^3, 1 \leq m \leq 10^5)\), representing the number of nodes and roads in the district, respectively.

Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\) \( (1 \leq u,v \leq n, 1 \leq w \leq 10^4)\) indicating that there is an undirected road between nodes \(u\) and \(v\) with length \(w\).

The following line contains a single integer \(Q\) \( (1 \leq Q \leq 10^5)\) denoting the number of queries.

Each of the next \(Q\) lines contains two integers \(s\) and \(t\) \( (1 \leq s,t \leq n)\) specifying a query to count the number of shortest paths from \(s\) to \(t\).

outputFormat

For each query, output a single integer on a new line: the number of shortest paths from \(s\) to \(t\). If there is no path, output 0.

sample

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

2
2