Wstęp do programowania w C++

Dzisiaj jest pierwszy dzień nowej pracy Jasia. Jaś musi dotrzeć do biura na czas. Może pojechać samochodem, jednak z powodu dużych korków rozważa również dojazd transportem publicznym. Może też podjechać kawałek samochodem i dopiero później przesiąść się do komunikacji miejskiej.

Znajdź najszybszą trasę od domu Jasia do biura. Jaś może całą drogę pokonać samochodem lub transportem publicznym. Może też przejechać część trasy samochodem i dopiero później się przesiąść. W momencie kiedy wsiądzie do transportu publicznego, nie może już skorzystać z samochodu (samochód został na parkingu lub pod domem).

Wejście

W pierwszej linii liczba skrzyżowań N.

Następnie liczba dróg C, które można pokonać samochodem (w obu kierunkach).

W kolejnych C liniach znajduje się opis ulic. Każda z nich składa się z trzech wartości:
C_i, C_j - numery połączonych skrzyżowań (numerowane od 1 do N),
C_v - czas potrzebny na pokonanie odcinka samochodem.

Następnie znajduje się liczba dwukierunkowych połączeń komunikacji miejskiej B.

Każda z kolejnych B linii zawiera trzy wartości:
B_i, B_j - numery połączonych skrzyżowań,
B_v - czas potrzebny na pokonanie drogi komunikacją miejską.

Na końcu znajdują się dwie wartości:
S - skrzyżowanie przy którym znajduje się dom Jasia,
E - skrzyżowanie przy którym znajduje się praca Jasia.

Zakresy danych:
1 ≤ N ≤ 100 000
1 ≤ C < 1 000 000
1 ≤ C_i, C_j ≤ N
C_v ≤ 1 000
1 ≤ B < 1 000 000
1 ≤ B_i, B_j ≤ N
B_v ≤ 1 000
1 ≤ S, E ≤ N

Wyjście

Na wyjściu należy wypisać jedną liczbę: najkrótszy czas potrzebny na przejazd z domu Jasia do jego nowego biura.

Przykład

Wejście:

5
4
1 2 12
2 4 10
1 3 15
3 5 1
1
4 5 1
1 4

Wyjście:

17

Wyjaśnienie do przykładu:

Jaś może pojechać samochodem od skrzyżowania 1 do 5 (przez 3) i wtedy przesiąść się do komunikacji miejskiej, żeby dojechać do biura.