W Bajtogórach znajduje się kurort narciarski Bajtyrk słynący z narciarskich tras biegowych. Są one bardzo malownicze, gdyż część z nich jest położona wysoko w górach lub w trudno dostępnych miejscach. Użytkownicy tras często korzystają z wyciągów ułatwiających dotarcie do niektórych z nich. Każdy wyciąg i każda trasa zaczyna się i kończy na określonej polanie. Trasy narciarskie nie mogą się przecinać, ale mogą przebiegać naturalnymi skalnymi tunelami i estakadami.

Trasy narciarskie mogą być jednokierunkowe lub dwukierunkowe. Podobnie, niektóre wyciągi (kolejki linowe) mogą być jedno lub dwukierunkowe.

Za korzystanie z wyciągów płaci się kartą magnetyczną. Karty kupuje się w kasach. Każda karta zawiera określoną liczbę punktów. Skorzystanie z każdego z wyciągów wiąże się z utratą pewnej liczby punktów zależnej od wyciągu. Niestety kasy nie zwracają pieniędzy za niewykorzystane punkty.

Bajtoni jest dziś na nartach ostatni dzień. Została mu jedna karta z pewną liczbą punktów, które chciałby wykorzystać do maksimum. Możesz założyc, że ta liczba punktów wystarczy na powrót do Bajtyrku.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego kur.in opis sieci tras i wyciągów oraz informacje o położeniu Bajtoniego i liczbie punktów na jego karcie,
• obliczy, z jaką najmniejszą liczbą punktów na karcie Bajtoni może dziś wrócić na dół, do Bajtyrku,
• zapisze wynik w pliku tekstowym kur.out.

Wejście

W pierwszym wierszu pliku tekstowego kur.in zapisane są dwie dodatnie liczby całkowite n i n', 1 <= n' < n <= 1000, oddzielone pojedynczym odstępem, oznaczające odpowiednio liczbę wszystkich polan oraz liczbę tych polan, które znajdują się na dole w samym Bajtyrku (są to polany o numerach od 1 do n' włącznie).

W drugim wierszu zapisana jest jedna dodatnia liczba całkowita k, 1 <= k <= 5000, równa łącznej liczbie wszystkich tras narciarskich. Każdy z kolejnych k wierszy zawiera po dwie różne dodatnie liczby całkowite, pooddzielane pojedynczymi odstępami, 1 <= p₁ <> p₂ < n. Liczby te oznaczają numer początkowej i końcowej polany danej trasy narciarskiej. Trasy dwukierunkowe są tu liczone dwukrotnie i reprezentowane w pliku wejściowym przez dwa (niekoniecznie kolejne) wiersze (postaci "p₁ p₂" i "p₂ p₁").

W k+3-cim wierszu zapisana jest jedna dodatnia liczba całkowita m, 1 <= m <= 300, równa liczbie wszystkich wyciągów. W kolejnych m wierszach opisane są wyciągi. W każdym z tych wierszy zapisane są trzy dodatnie liczby całkowite q₁, q₂ i r, pooddzielane pojedynczymi odstępami. Liczby q₁ i q₂ oznaczają odpowiednio numer polany, na której wyciąg się zaczyna i numer polany, na której się kończy, 1 <= q₁ <> q₂ <= n. Liczba r jest równa liczbie punktów, które trzeba zapłacić za przejazd wyciągiem, 1 <= r <= 1000. Wyciągi dwukierunkowe (kolejki linowe) są tu liczone dwukrotnie i reprezentowane w pliku wejściowym przez dwa (niekoniecznie kolejne) wiersze (postaci "q₁ q₂ r₁" i "q₂ q₁ r₂"). Ceny przejazdu wyciągiem w jedną i w drugą stronę mogą być różne.

W ostatnim wierszu zapisane są dwie dodatnie liczby całkowite b i s, oddzielone pojedynczym odstępem, 1 <= b <= n, 1 <= s <= 2000. Pierwsza z nich oznacza numer polany, na której znajduje się Bajtoni a druga jest równa liczbie punktów na jego ostatniej karcie magnetycznej.

Wyjście

Twój program powinien zapisać w pierwszym (i jedynym) wierszu pliku tekstowego kur.out jedną liczbę całkowitą, równą najmniejszej możliwej liczbie punktów, z jaką Bajtoni może wrócić do Bajtyrku.

Przykład

Dla pliku wejściowego 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 9

1