Znajdujesz się na łańcuchu o długości $n$, ale możesz przemieszczać się między różnymi pozycjami jedynie za pomocą portali. Użycie portalu wymaga określonego czasu. Twoim zadaniem jest obliczenie dla każdej pozycji minimalnego czasu potrzebnego na dotarcie do niej lub stwierdzenie, że jest ona nieosiągalna.

Portal składa się z dwóch stron: jedna prowadzi z $u$ do $v$, a druga z $x$ do $y$. Portale są dwukierunkowe, co oznacza, że jeśli stoisz w dowolnym miejscu na odcinku od $u$ do $v$, możesz przenieść się w dowolne miejsce na odcinku od $x$ do $y$ i odwrotnie. Możesz również używać portalu wielokrotnie, co oznacza, że jeśli jesteś na odcinku od $u$ do $v$, możesz wykonać dwa skoki, aby dotrzeć w dowolne miejsce na odcinku od $u$ do $v$.

Wejście

Pierwsza linia zawiera trzy liczby całkowite $n, m, s$, oznaczające liczbę węzłów, liczbę portali oraz Twoją pozycję startową.

Następnie $m$ linii, z których każda zawiera 5 liczb całkowitych $u\ v\ x\ y\ t$, gdzie $1 \le u, v, x, y \le n$, opisujących końce portalu oraz czas potrzebny na jego użycie.

Wyjście

Wypisz jedną linię zawierającą $n$ liczb całkowitych, gdzie $i$-ta liczba oznacza czas potrzebny na dotarcie z $s$ do $i$. Jeśli pozycja jest nieosiągalna, wypisz $-1$.

Przykład

Przykład 1 Wejście

6 2 1
1 1 2 3 0
3 3 5 6 0

Przykład 1 Wyjście

0 0 0 -1 0 0

Podzadania

Dla $100\%$ danych wejściowych zachodzą warunki: $n, m \le 10^3, 0 \le t \le 10^5$.