Upgraded Minimum Travel Time

You are given a weighted undirected graph with N junctions and M streets. Each street connects two junctions and has a travel time. Additionally, there are K possible upgrades. Each upgrade specifies a street (given by two endpoints) that can be upgraded to have a lower travel time.

Your task is to determine the minimum travel time from junction A to junction B, if you can apply at most one upgrade (or choose not to upgrade any street). Formally, let the original travel time be computed without any upgrades. Then for each available upgrade, you simulate reducing the travel time of that street to a new value. The answer is the minimum possible travel time among the original configuration and all configurations after applying exactly one upgrade.

The problem can be modeled using Dijkstra's algorithm. Some of the formulas you may encounter include the update step in Dijkstra's algorithm:

\[ dist[v] = \min\left(dist[v],\; dist[u] + w(u,v)\right) \]

inputFormat

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

N M K
u1 v1 t1
u2 v2 t2
... (M lines for streets)
x1 y1 r1
x2 y2 r2
... (K lines for upgrades)
A B

</p>

Where:

• N is the number of junctions (numbered from 1 to N).
• M is the number of streets.
• K is the number of available upgrades.
• Each of the following M lines contains three integers u, v, and t representing a bidirectional street between junctions u and v with travel time t.
• Each of the next K lines contains three integers x, y, and r representing an upgrade on the street between junctions x and y, reducing its travel time to r.
• The final line contains two integers A and B which represent the starting and destination junctions, respectively.

outputFormat

Output a single integer, the minimum travel time to go from junction A to junction B after applying at most one upgrade. The answer is printed to the standard output (stdout).

## sample

5 5 1
1 2 10
2 3 10
3 4 10
4 5 10
1 5 50
1 5 5
1 5

5