Po jednej krowie z każdej z $N$ farm ($1 \le N \le 1000$), ponumerowanych $1..N$, wybiera się na wielką krowią imprezę na farmie $X$ ($1 \le X \le N$). Łącznie $M$ ($1 \le M \le 100,000$) dróg jednokierunkowych łączy pary farm; przejście drogi $i$ zajmuje $T_i$ ($1 \le T_i \le 100$) jednostek czasu.

Każda krowa musi dojść na imprezę, a po jej zakończeniu wrócić na swoją farmę. Każda jest leniwa, więc wybiera optymalną trasę o najkrótszym czasie. Ponieważ drogi są jednokierunkowe, trasa powrotna może różnić się od trasy na imprezę.

Jaki jest najdłuższy, wśród wszystkich krów, czas potrzebny jednej krowie na dojście na imprezę i powrót?

Wejście

Wczytaj dane ze standardowego wejścia.

• Wiersz 1: trzy liczby całkowite oddzielone spacjami: odpowiednio $N$, $M$ i $X$.

Wiersze $2..M+1$: wiersz $i+1$ opisuje drogę $i$ trzema liczbami całkowitymi oddzielonymi spacjami: $A_i$, $B_i$ i $T_i$. Droga prowadzi z farmy $A_i$ do farmy $B_i$, a jej przejście zajmuje $T_i$ jednostek czasu.

Wyjście

Wypisz dane na standardowe wyjście.

• Wiersz 1: jedna liczba całkowita, maksymalny czas marszu jednej krowy.

Przykład

Wejście 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Wyjście 1

10

Uwagi

Krowa $4$ idzie bezpośrednio na imprezę ($3$ jednostki) i wraca przez farmy $1$ i $3$ ($7$ jednostek), łącznie $10$ jednostek czasu.

Źródło zadania: USACO 2007 February Silver