Resort

Memory limit: 32 MB

In Byte Mountains there is a ski resort Bytegary. It is famous for its cross-country ski tracks. They are very picturesque because a part of them lies high in the mountains or in places hard to reach. Users of the tracks often make use of ski lifts that help reach some of the tracks. Each lift and each track starts and ends on a particular clearing. The ski tracks must not cross but they may run through natural rock tunnels or bridges.

The ski tracks may be one-way or two-way. Similarly, some ski lifts may be one- or two-way.

Using a ski lift is charged by means of magnetic cards. The cards can be bought at cash desks. Each card contains a particular number of points. Using each ski lift is connected with loosing some number of points, depending on the lift. Unfortunately, the cash desks do not refund unused points.

Today is the last day Byteoni is skiing. He has one card with some number of points left which he wants to use maximally. You may assume that the number of points is enough to return to Bytegary.

Task

Write a program which:

• reads from the standard input the description of the network of tracks and ski lifts and the information on Byteoni's position and the number of points on his card,
• computes the smallest possible number of points that can be left on Byteoni's card on his return down to Bytegary,
• writes the result to the standard output.

Input

In the first line of the standard input there are two positive integers and , , separated by a single space. They, respectively, denote the number of all the clearings and the number of those clearings that lie down right in Bytegary (those are the clearings numbered to inclusive).

In the second line there is one positive integer , , equal to the total number of all ski tracks. Each of the successive lines contains two distinct positive integers, separated by a single space, . Those figures denote the numbers of the starting and the ending clearings of the given ski track. Two-way tracks are counted twice, and are represented in the input by two (not necessarily consecutive) lines (of the form " " and " ").

In the line number there is one positive integer , , equal to the number of all the ski lifts. In the successive lines the lifts are described. In each of those lines three positive integers , and are written; they are separated by single spaces. The numbers and denote the numbers of the clearings the lift starts and ends, respectively, . The number equals the number of points that is charged for the lift ride, . Two-way ski lifts are counted twice, and are represented in the input by two (not necessarily consecutive) lines (of the form " " and " "). The price for the ski lift ride in one direction may differ from the price for the ride in the other direction.

In the last line there are two positive integers and , separated by a single space , . The former is the number of the clearing Byteoni is present on, and the latter equals the number of points on his last magnetic card.

Output

Your program should write one integer in the first (and only) line of the standard output. This number should be equal to the smallest possible number of points left over on Byteoni's return to Bytegary.

Example

For the input data:

5 2
6
3 2
3 5
1 5
3 4
1 2
4 3
4
3 1 1
4 3 5
5 2 2
3 4 5
4 9

the correct result is:

1

Task author: Marcin Sawicki.