Une vache de chacune des $N$ fermes ($1 \le N \le 1000$), numérotées $1..N$, va assister à une grande fête bovine à la ferme $X$ ($1 \le X \le N$). Au total, $M$ ($1 \le M \le 100,000$) routes à sens unique relient des paires de fermes ; parcourir la route $i$ prend $T_i$ ($1 \le T_i \le 100$) unités de temps.

Chaque vache doit marcher jusqu’à la fête puis, une fois celle-ci terminée, retourner à sa ferme. Chaque vache est paresseuse et choisit donc un itinéraire optimal de durée minimale. Comme les routes sont à sens unique, le trajet retour peut être différent du trajet aller.

Parmi toutes les vaches, quelle est la plus longue durée qu’une vache doit consacrer à l’aller-retour jusqu’à la fête ?

Entrée

Lisez l’entrée depuis l’entrée standard.

• Ligne 1 : trois entiers séparés par des espaces, respectivement $N$, $M$ et $X$.

Lignes $2..M+1$ : la ligne $i+1$ décrit la route $i$ avec trois entiers séparés par des espaces : $A_i$, $B_i$ et $T_i$. Cette route va de la ferme $A_i$ à la ferme $B_i$ et prend $T_i$ unités de temps à parcourir.

Sortie

Écrivez la sortie sur la sortie standard.

• Ligne 1 : un entier, la durée maximale de marche pour une vache.

Exemples

Entrée 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

Sortie 1

10

Remarque

La vache $4$ va directement à la fête ($3$ unités) et revient par les fermes $1$ et $3$ ($7$ unités), pour un total de $10$ unités de temps.

Origine du problème : USACO 2007 February Silver