Shortest Route with Closed Tunnels

You are given an undirected graph representing a network of tunnels connecting various stations. Each tunnel has an associated travel time. Additionally, some tunnels may be closed for maintenance. Your task is to compute the shortest travel time from a starting station s to a destination station d, while avoiding the closed tunnels. If there is no possible route under the given constraints, output UNREACHABLE.

The problem can be modeled using a weighted graph, where the distance update follows the Dijkstra algorithm: \[ d[v] = \min(d[v], d[u] + w(u,v)) \] for each edge \((u,v)\) with weight \(w(u,v)\).

Note that the graph is undirected, so each tunnel connects two stations in both directions. Closed tunnels should be omitted from the graph before running the shortest path algorithm.

inputFormat

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

n m
u1 v1 w1
u2 v2 w2
... (m lines of tunnel information)
 s d
 k
 (k lines of closed tunnels, each containing two integers: u and v)

Where:

• n is the number of stations.
• m is the number of tunnels.
• Each of the next m lines contains three integers u, v and w representing a tunnel between station u and station v with travel time w.
• The following line contains two integers: s (starting station) and d (destination station).
• The next line contains an integer k, the number of closed tunnels.
• Then follow k lines each with two integers representing a closed tunnel between two stations.

outputFormat

Output the shortest travel time from station s to station d via standard output (stdout). If no route exists, output UNREACHABLE. The output should be exactly one line.

## sample

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

15

</p>