P1821 [USACO07FEB] Cow Party S

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.

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 one line with one integer representing the answer.

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