Resort

In the Byte Mountains there is a ski resort called Bytegary, famous for its cross-country ski tracks. Every track and every lift starts at one clearing and ends at another.

• A ski track is a directed edge and is free to use. A two-way track is represented as two one-way tracks, one in each direction.
• A ski lift is a directed edge; riding it once deducts a fixed number of points from your magnetic card, and unused points are never refunded. A two-way lift is likewise represented as two one-way lifts, and the cost may differ between the two directions.

Byteoni is currently at clearing $b$ with $s$ points left on his last card. He wants to get down to one of the base clearings at the foot of Bytegary (those numbered $1$ through $n'$), leaving as few points on the card as possible.

He may ride any track for free, and may ride a lift only when his current number of points is at least that lift's cost. You may assume it is always possible for him to reach a base clearing (he never gets stranded for lack of points).

Compute the smallest number of points that can be left on Byteoni's card when he reaches a base clearing.

• The first line contains two integers $n$ and $n'$ separated by a single space ($1 \le n' < n \le 1000$). $n$ is the total number of clearings, numbered $1$ through $n$; the base clearings are those numbered $1$ through $n'$.
• The second line contains the number of ski tracks $k$ ($1 \le k \le 5000$).
• Each of the next $k$ lines contains two distinct integers $p_1$ and $p_2$ ($1 \le p_1 \ne p_2 \le n$), a one-way track from $p_1$ to $p_2$.
• The next line contains the number of lifts $m$ ($1 \le m \le 300$).
• Each of the next $m$ lines contains three integers $q_1$, $q_2$ and $r$ ($1 \le q_1 \ne q_2 \le n$, $1 \le r \le 1000$), a one-way lift from $q_1$ to $q_2$ costing $r$ points.
• The last line contains two integers $b$ and $s$ ($1 \le b \le n$, $1 \le s \le 2000$): the clearing Byteoni stands on and the number of points on his last card.

Output a single integer: the smallest number of points that can be left on the card when Byteoni reaches a base clearing.