Minimum Travel Distance

In the country of Algorithmia, there are several towns connected by both roads and highways. Each road or highway has an associated distance. Given the number of towns, a list of roads, a list of highways, and two specific towns (a start town (s) and a destination town (d)), your task is to compute the minimum distance required to travel from (s) to (d) using any combination of roads and highways. If no such path exists, output -1.

The problem can be solved using Dijkstra's algorithm. Consider the roads and highways as undirected edges with non-negative weights, and find the shortest path between the two given towns.

inputFormat

Input is read from standard input (stdin) in the following format:

1. The first line contains two integers (n) and (m), where (n) is the number of towns and (m) is the number of road connections.
2. The next (m) lines each contain three integers (u), (v), and (w), denoting a road connecting towns (u) and (v) with distance (w).
3. A line containing an integer (k), the number of highway connections.
4. The next (k) lines each contain three integers (x), (y), and (z), denoting a highway between towns (x) and (y) with distance (z).
5. The final line contains two integers (s) and (d), representing the starting and destination towns respectively.

outputFormat

Output a single integer to standard output (stdout): the minimum travel distance from town (s) to town (d). If no valid path exists, output -1.## sample

5 6
1 2 4
1 3 2
2 3 1
3 4 7
2 4 3
4 5 1
2
3 5 2
1 5 8
1 5

4