Shortest Paths Under Distance Constraint

You are given an undirected graph representing a network of cities connected by roads. Each road has an associated length in miles. Your task is to answer several queries. For each query, you need to determine the shortest path distance between two cities. However, the path is acceptable only if its total distance does not exceed a given limit \(d\) miles. If no such path exists, output -1.

Note: The cities are labeled from 1 to \(n\). Each road connects two cities and can be traversed in both directions.

Example:

For \(n=4\), \(m=5\), \(d=6\), and the roads:

• 1 2 2
• 2 3 2
• 3 4 2
• 4 1 2
• 1 3 6

With queries: (1, 3), (1, 4) and (2, 4), the answers are: 4 2 4 because the shortest path from 1 to 3 is of length 4 = 1→2→3, from 1 to 4 is of length 2 = 1→4, and from 2 to 4 is 4 = 2→1→4.

inputFormat

The input is given from the standard input in the following format:

The first line contains three integers (n), (m), and (d) where:

• (n) is the number of cities.
• (m) is the number of roads.
• (d) is the maximum allowed distance.

The next (m) lines each contain three integers (u), (v), and (l) representing a road between cities (u) and (v) with length (l) miles.

The next line contains a single integer (q) representing the number of queries.

Each of the following (q) lines contains two integers (a) and (b) asking for the shortest path distance from city (a) to city (b) (if the distance is within (d), otherwise output -1).

outputFormat

For each query, output the shortest path distance if it does not exceed (d) miles, otherwise output -1. The results for all queries should be printed in one line, separated by spaces, to the standard output.## sample

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

4 2 4