Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_12_13 - Dojazd do pracy

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:
Ci, Cj - numery połączonych skrzyżowań (numerowane od 1 do N),
Cv - 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:
Bi, Bj - numery połączonych skrzyżowań,
Bv - 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 ≤ Ci, CjN
Cv ≤ 1 000
1 ≤ B < 1 000 000
1 ≤ Bi, BjN
Bv ≤ 1 000
1 ≤ S, EN

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.


Dodane przez:Grzegorz Spryszyński
Data dodania:2021-01-11
Limit czasu wykonania programu:1s-2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.