編號為 $1..N$ 的 $N$ 座農場（$1 \le N \le 1000$）各有一頭牛要去農場 $X$（$1 \le X \le N$）參加盛大的牛隻派對。共有 $M$ 條（$1 \le M \le 100,000$）單向道路連接農場對；經過道路 $i$ 需要 $T_i$（$1 \le T_i \le 100$）個時間單位。

每頭牛都必須步行去參加派對，並在派對結束後返回自己的農場。每頭牛都很懶，因此會選擇耗時最短的最佳路線。由於道路是單向的，回程路線可能與前往派對的路線不同。

在所有牛中，步行去參加派對再返回所需的最長時間是多少？

輸入格式

從標準輸入讀取輸入。

• 第 1 行：三個以空格分隔的整數，依次為 $N$、$M$ 和 $X$。

第 $2..M+1$ 行：第 $i+1$ 行以三個空格分隔的整數 $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