Dla kondycji $N$ krów ($(2 \le N \le 1,000,000)$) biegnie sztafetę na $T$ ścieżkach ($(2 \le T \le 100)$) pastwiska.

Każda łączy dwa różne skrzyżowania ($(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$), każde jest końcem co najmniej dwóch ścieżek. Długość $length_i$ ($(1 \le length_{i} \le 1,000)$) i końce znane; nie ma dwóch bezpośrednich ścieżek między parą. To graf matematyczny.

$N$ krów stoi na skrzyżowaniach, kilka może na tym samym. Muszą dobrze stać, by przekazywać pałeczkę krowa po krowie do mety.

Pomóż ustawieniu: najkrótsza droga między $S$ i $E$ po dokładnie $N$ ścieżkach.

Wejście

• Wiersz $1$: całkowite $N$, $T$, $S$, $E$ oddzielone.

• Wiersze $2..T+1$: wiersz $i+1$ opisuje ścieżkę $i$ przez $length_i$, $I1_i$, $I2_i$ oddzielone.

Wyjście

• Wiersz $1$: jedno całkowite, najkrótsza odległość $S$ do $E$ po dokładnie $N$ ścieżkach.

Przykład

Wejście 1

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

Wyjście 1

10

Autor zadania: Erik Bernhardsson, 2003