Uma vaca de cada uma das $N$ quintas ($1 \le N \le 1000$), numeradas $1..N$, vai participar na grande festa bovina na quinta $X$ ($1 \le X \le N$). Um total de $M$ ($1 \le M \le 100,000$) estradas de sentido único liga pares de quintas; percorrer a estrada $i$ requer $T_i$ ($1 \le T_i \le 100$) unidades de tempo.

Cada vaca deve caminhar até à festa e regressar à sua quinta quando a festa terminar. Todas as vacas são preguiçosas e escolhem um percurso ótimo com o menor tempo. Como as estradas são de sentido único, o percurso de regresso pode diferir do percurso de ida.

Entre todas as vacas, qual é o maior tempo que uma vaca tem de passar a caminhar até à festa e de volta?

Entrada

Leia os dados da entrada padrão.

• Linha 1: três inteiros separados por espaços, respetivamente $N$, $M$ e $X$.

Linhas $2..M+1$: a linha $i+1$ descreve a estrada $i$ com três inteiros separados por espaços: $A_i$, $B_i$ e $T_i$. A estrada vai da quinta $A_i$ à quinta $B_i$ e requer $T_i$ unidades de tempo para ser percorrida.

Saída

Escreva os dados na saída padrão.

• Linha 1: um inteiro, o maior tempo que uma vaca tem de caminhar.

Exemplos

Entrada 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

Saída 1

10

Note

A vaca $4$ vai diretamente à festa ($3$ unidades) e regressa pelas quintas $1$ e $3$ ($7$ unidades), num total de $10$ unidades de tempo.

Origem do problema: USACO 2007 February Silver