Minimum Travel Time with Traffic Updates

You are given a network of n cities and m bidirectional roads. Each road connects two different cities and has an initial travel time. In addition, there are k traffic update events. Each event increases the travel time of a specific road by a given delta. Your task is to compute the minimum travel time from a starting city to a destination city after applying all traffic updates.

The input provides the number of cities and roads, followed by the description of each road. Then, you are given the starting city, the destination city, and the number of traffic updates. Finally, the updates are given, where each update specifies a road (by its two endpoints) and the additional travel time introduced by traffic conditions.

If the destination is unreachable, print -1.

inputFormat

The input is given via standard input with the following format:

 n m
 u1 v1 t1
 u2 v2 t2
 ...
 um vm tm
 start end
 k
 x1 y1 delta1
 x2 y2 delta2
 ...
 xk yk deltak

Here, n is the number of cities, m is the number of roads. Each of the next m lines describes a road between cities u and v with travel time t. The next line contains two integers: the start city and the destination city. Then an integer k is given, representing the number of traffic updates. The following k lines each contain three integers x, y, and delta, indicating that the travel time between city x and y increases by delta.

outputFormat

Print a single integer representing the minimum travel time from the starting city to the destination city after applying all the traffic updates. If the destination is unreachable, print -1.

## sample

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

11

</p>