Je daný jednoduchý ovahovaný graf a dva jeho vrcholy. Zistite dĺžku najkratšej cesty medzi nimi.
Na prvom riadku sú dve čísla $n$ a $m$ ($1 \leq n \leq 10^5$, $1 \leq m \leq 3 \cdot 10^5$), udávajúce počet vrcholov grafu.
Nasleduje $m$ riadkov, každý obsahuje trojicu čísel $a_i, b_i, w_i$, kde $w_i$ ($1 \leq w_i \leq 10^6$) je vaha hrany medzi vrcholmi $a_i$ a $b_i$ (vrcholy grafu sú číslované od jednotky).
Na poslednom riadku je dvojica čísel, označujúcich vrcholy, cesta medzi ktorými nás zaujíma.
Výstup má pozostávať z jediného čísla: dĺžky najkratšej cesty. Ak žiadna neexistuje, tak vypíšte $-1$.
3 3
1 2 214
2 3 465
1 3 260
1 2
214
7 6
1 2 231
2 3 286
1 4 27
4 5 1000
3 5 303
5 7 430
1 5
820