Minimal Toll Cost

Given a network of cities connected by roads with toll costs, some roads are unavailable due to maintenance or other issues. Your task is to find the minimal total toll cost to travel from a starting city (s) to a destination city (d) without using any unavailable roads.

The problem can be modeled as a weighted undirected graph where each edge represents a road with an associated toll cost. However, certain edges (roads) are marked as unavailable and cannot be used. The goal is to compute the minimum cost path from (s) to (d), or output (-1) if no such path exists.

This problem can be efficiently solved using Dijkstra's algorithm with the modification of skipping unavailable roads.

inputFormat

The input is read from standard input (stdin) with the following format:

• The first line contains two integers (n) and (m): the number of cities and the number of roads.

• The next (m) lines each contain three integers (u), (v), and (c), describing a road between cities (u) and (v) with a toll cost (c).

• The following line contains an integer (k), the number of unavailable roads.

• The next (k) lines each contain two integers (p) and (q), indicating that the road between cities (p) and (q) is unavailable.

• The last line contains two integers (s) and (d), representing the starting city and the destination city respectively.

outputFormat

Output a single integer to standard output (stdout): the minimal total toll cost required to travel from city (s) to city (d). If there is no valid path, output (-1).## sample

5 6
1 2 5
1 3 10
2 4 2
3 4 1
4 5 3
2 5 9
1
1 4
1 5

10