Una vaca de cada una de $N$ granjas ($1 \le N \le 1000$), numeradas $1..N$, irá a la gran fiesta bovina en la granja $X$ ($1 \le X \le N$). Un total de $M$ ($1 \le M \le 100,000$) carreteras de sentido único conecta pares de granjas; recorrer la carretera $i$ requiere $T_i$ ($1 \le T_i \le 100$) unidades de tiempo.

Cada vaca debe caminar hasta la fiesta y regresar a su granja cuando termine. Todas las vacas son perezosas y eligen una ruta óptima de menor duración. Como las carreteras son de sentido único, la ruta de regreso puede diferir de la ruta de ida.

Entre todas las vacas, ¿cuál es el mayor tiempo que una vaca debe dedicar a caminar hasta la fiesta y regresar?

Entrada

Lee los datos de la entrada estándar.

• Línea 1: tres enteros separados por espacios, respectivamente $N$, $M$ y $X$.

Líneas $2..M+1$: la línea $i+1$ describe la carretera $i$ con tres enteros separados por espacios: $A_i$, $B_i$ y $T_i$. La carretera va de la granja $A_i$ a la granja $B_i$ y requiere $T_i$ unidades de tiempo para recorrerla.

Salida

Escribe los datos en la salida estándar.

• Línea 1: un entero, el tiempo máximo que debe caminar una vaca.

Ejemplos

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

Salida 1

10

Nota

La vaca $4$ va directamente a la fiesta ($3$ unidades) y regresa por las granjas $1$ y $3$ ($7$ unidades), para un total de $10$ unidades de tiempo.

Origen del problema: USACO 2007 February Silver