Dāvana

Auseklis un Gaisma dzīvo īpatnējā pilsētā, kurā ir $N$ ēkas, sanumurētas no $1$ līdz $N$. Pilsētā ir $N-1$ divvirzienu ceļa posms. Katrs ceļa posms savieno divas ēkas un no katras ēkas uz katru citu ir iespējams nokļūt, braucot pa vienu vai vairākiem ceļa posmiem. Auseklis dzīvo ēkā ar numuru $a$, bet Gaisma - $g$. Pilsētā ir $V$ veikali, kas atrodas ēkās ar numuriem $v_1, v_2, \ldots, v_V$.

Šodien ir Gaismas dzimšanas diena un Auseklis ir uzaicināts uz svinībām. Auseklis plāno pa ceļam aizbraukt uz kādu veikalu un nopirkt dāvanu. Viņš labi zina, kādas dāvanas Gaismai patīk, un ir izpētījis to cenas visos veikalos. Katram ceļa posmam Auseklis arī zina, cik viņam izmaksātu degviela, kas nepieciešama, lai aizbrauktu no viena šī ceļa posma gala līdz otram. Katram ceļa posmam brauciena izmaksas abos virzienos ir vienādas. Auseklis ir taupīgs - viņš vēlas degvielai un dāvanai kopumā iztērēt pēc iespējas mazāk naudas. Palīdzi Auseklim izrēķināt, kāds ir mazākais naudas daudzums, kas viņam nepieciešams, lai no savas mājas aizbrauktu uz vienu no veikaliem, nopirktu dāvanu un aizbrauktu pie Gaismas.

Viens ēku un ceļu posmu shematisks attēls parādīts attēlā. Auseklis dzīvo 2. ēkā, bet Gaisma - 5. ēkā. Dāvanu iespējams nopirkt 1., 3., 4. vai 6. ēkā. Dāvanu cenas šajos veikalos ir attiecīgi 5, 1, 9 un 3, bet ceļa izmaksas aizbraukšanai uz veikalu un pie Gaismas ir attiecīgi 9, 7, 3 un 5. Vislētākās kopējās izmaksas (8) Auseklis var iegūt, pērkot dāvanu 3. vai 6. ēkā.

Pirmajā rindā doti četri naturāli skaitļi - ēku skaits $N$ ($N \leq 2 \cdot 10^5$), veikalu skaits $V$ ($V \leq N$) un ēku, kurās dzīvo Auseklis un Gaisma, numuri $a$ un $g$ ($1 \leq a, g \leq N$).

Nākamajās $N - 1$ rindās katrā doti trīs naturāli skaitļi $u_i$, $v_i$, $w_i$ ($u_i \neq v_i$, $1 \leq u_i, v_i \leq N$, $1 \leq w_i \leq 10^9$), kas norāda, ka $i$-tais ceļa posms savieno ēkas $u_i$ un $v_i$ un aizbraukšanas no vienas ēkas uz otru izmaksas ir $w_i$.

Nākamajās $V$ rindās katrā doti divi naturāli skaitļi - ēkas, kurā atrodas veikals, numurs $e_i$ ($1 \leq e_i \leq N$) un dāvanas cena šajā veikalā $c_i$ ($1 \leq c_i \leq 10^9$). Visi $e_i$ ir atšķirīgi.

Izvaddatu vienīgajā rindā jābūt vienam naturālam skaitlim - minimālajam naudas daudzumam, kas Auseklim nepieciešams dāvanai un ceļam.