


Ski Resort
In Byte Mountains there is a ski resort Bytegary. It is famous for its crosscountry 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 oneway or twoway. Similarly, some ski lifts may be one or twoway. 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. TaskWrite a program which:
InputIn the first line of the text file kur.in there are two positive integers n and n', 1 <= n' < n <= 1000, 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 1 to n' inclusive).In the second line there is one positive integer k, 1 <= k <= 5000, equal to the total number of all ski tracks. Each of the successive k lines contains two distinct positive integers, separated by a single space, 1 <= p_{1} <> p_{2} < n. Those figures denote the numbers of the starting and the ending clearings of the given ski track. Twoway tracks are counted twice, and are represented in the input file by two (not necessarily consecutive) lines (of the form "p_{1} p_{2}" and "p_{2} p_{1}"). In the line number k+3 there is one positive integer m, 1 <= m <= 300, equal to the number of all the ski lifts. In the successive m lines the lifts are described. In each of those lines three positive integers q_{1}, q_{2} and r are written; they are separated by single spaces. The numbers q_{1} and q_{2} denote the numbers of the clearings the lift starts and ends, respectively, 1 <= q_{1} <> q_{2} <= n. The number r equals the number of points that is charged for the lift ride, 1 <= r <= 1000. Twoway ski lifts are counted twice, and are represented in the input file by two (not necessarily consecutive) lines (of the form "q_{1} q_{2} r_{1}" and "q_{2} q_{1} r_{2}"). 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 b and s, separated by a single space 1 <= b <= n, 1 <= s <= 2000. 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. OutputYour program should write one integer in the first (and only) line of the text file kur.out. This number should be equal to the smallest possible number of points left over on Byteoni's return to Bytegary.ExampleFor the following input file kur.in: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 9the correct answer is in the following output file kur.out: 1 Print friendly version 