Description

Winter break has arrived, and $n$ cows are going to attend a party held at the farm of the cow numbered $x$. There are $m$ directed roads between farms, and each road has a certain length.

After the party, every cow must return home. Whether going to the party or going back home, each cow will choose the shortest path. Among these $n$ cows, find the maximum length of a shortest round-trip path.

Input Format

The first line contains three integers representing the number of cows $n$, the number of roads $m$, and the party farm index $x$.
The next $m$ lines each contain three integers $u, v, w$, indicating that there is a road from $u$ to $v$ with length $w$.

Output Format

Output one line with one integer representing the answer.

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

10

Hint

Sample 1 Explanation

Constraints For all test points, it is guaranteed that $1 \leq x \leq n \leq 10^3$, $1 \leq m \leq 10^5$, $1 \leq u, v \leq n$, $1 \leq w \leq 10^2$. It is guaranteed that from any node you can reach node $x$, and from $x$ you can reach all other nodes.

Translated by ChatGPT 5