Una mucca da ciascuna delle $N$ fattorie ($1 \le N \le 1000$), numerate $1..N$, parteciperà alla grande festa bovina nella fattoria $X$ ($1 \le X \le N$). Un totale di $M$ ($1 \le M \le 100,000$) strade a senso unico collega coppie di fattorie; percorrere la strada $i$ richiede $T_i$ ($1 \le T_i \le 100$) unità di tempo.

Ogni mucca deve camminare fino alla festa e tornare alla propria fattoria quando la festa finisce. Ogni mucca è pigra e sceglie quindi un percorso ottimale con il minor tempo. Poiché le strade sono a senso unico, il percorso di ritorno può essere diverso da quello di andata.

Tra tutte le mucche, qual è il tempo più lungo che una mucca deve impiegare per camminare fino alla festa e tornare?

Input

Leggi i dati dall’input standard.

• Riga 1: tre interi separati da spazi, rispettivamente $N$, $M$ e $X$.

Righe $2..M+1$: la riga $i+1$ descrive la strada $i$ con tre interi separati da spazi: $A_i$, $B_i$ e $T_i$. La strada va dalla fattoria $A_i$ alla fattoria $B_i$ e richiede $T_i$ unità di tempo per essere percorsa.

Output

Scrivi i dati sull’output standard.

• Riga 1: un intero, il massimo tempo che una mucca deve camminare.

Esempi

Input 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

Output 1

10

Note

La mucca $4$ va direttamente alla festa ($3$ unità) e torna attraverso le fattorie $1$ e $3$ ($7$ unità), per un totale di $10$ unità di tempo.

Origine del problema: USACO 2007 February Silver