Taco Toll: Minimum Toll Problem

You are given a connected undirected graph representing a network of cities where each edge has an associated toll cost. Your task is to determine for a given set of queries whether it is possible to travel from one city to another within a given budget. If it is possible, you must find the minimum toll cost required for that journey.

More formally, you are given an undirected graph with n cities and m roads. Each road connects two cities u and v with a toll cost c. Then, for each query that consists of two cities a, b and a maximum allowable budget B, determine if the minimum toll cost (computed using the classic Dijkstra's algorithm) from city a to city b is less than or equal to B. If yes, output YES d where d is the minimum toll cost; otherwise, output NO.

The underlying mathematical formulation for the toll cost is given by:

[ \text{Let } d(a,b) = \min_{\text{paths } P \text{ from } a \text{ to } b} \sum_{(u,v) \in P} c(u,v) ]

You need to process multiple queries efficiently.

inputFormat

The input is given via stdin and has the following format:

 n m
 u1 v1 c1
 u2 v2 c2
 ...
 um vm cm
 k
 a1 b1 B1
 a2 b2 B2
 ...
 ak bk Bk

Where:

• n is the number of cities.
• m is the number of roads.
• Each of the next m lines describes a road between two cities u and v with a toll cost c.
• k is the number of queries.
• Each of the next k lines contains three integers: a (starting city), b (destination city), and B (maximum toll budget).

outputFormat

The output should be written to stdout. For each query, output a single line:

• If there is a path from city a to city b such that the minimum toll cost is less than or equal to B, print YES d where d is the computed minimum toll cost.
• If no such path exists, print NO.

## sample

4 4
1 2 10
2 3 10
3 4 10
4 1 10
3
1 3 25
1 4 5
2 4 20

YES 20
NO
YES 20

</p>