Description

Original source: USACO 2007 Feb. Silver

$N (1 \le N \le 1000)$ cows are going to attend a party held at the farm of cow numbered $x(1 \le x \le N)$. There are $M(1\le M \le 100000)$ directed roads, each with a length of $T_i(1 \le T_i \le 100)$. Every cow must attend the party and then return home, and each cow will choose the shortest path. Find the length of the longest shortest path (a round trip) among all $N$ cows. Special note: there may be multiple edges with different weights.

Input Format

Line $1$: $3$ space-separated integers $N,M,X$;

Lines $2 \ldots M+1$: $3$ space-separated integers $A_i, B_i, T_i$, indicating a road from $A_i$ to $B_i$ with length $T_i$.

Output Format

A single integer representing the length of the longest shortest path.

Sample 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

10