$1..N$ と番号付けされた $N$ 個の農場（$1 \le N \le 1000$）から 1 頭ずつの牛が、農場 $X$（$1 \le X \le N$）で開かれる大きな牛のパーティーに参加します。農場同士を結ぶ一方通行の道路が合計 $M$ 本（$1 \le M \le 100,000$）あり、道路 $i$ を通るには $T_i$（$1 \le T_i \le 100$）単位の時間がかかります。

各牛はパーティーへ歩いて行き、終わったら自分の農場に戻らなければなりません。牛は皆怠け者なので、所要時間が最短の最適な経路を選びます。道路は一方通行なので、帰りの経路は行きの経路と異なる場合があります。

すべての牛の中で、パーティーへの往復にかかる最長の時間はいくつでしょうか？

入力

標準入力から入力を読み込んでください。

• 1 行目：空白で区切られた 3 つの整数 $N$、$M$、$X$ がこの順に与えられます。

$2..M+1$ 行目：$i+1$ 行目は、空白区切りの 3 つの整数 $A_i$、$B_i$、$T_i$ で道路 $i$ を表します。この道路は農場 $A_i$ から農場 $B_i$ に向かい、通行に $T_i$ 単位の時間がかかります。

出力

標準出力に出力してください。

• 1 行目：ある牛が歩く必要のある時間の最大値を表す整数。

入出力例

入力 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

出力 1

10

注記

牛 $4$ は直接パーティーへ向かい（$3$ 単位）、農場 $1$ と $3$ を経由して戻ります（$7$ 単位）。合計は $10$ 単位です。

出典：USACO 2007 February Silver