Longest Round-Trip Time for Cows

During the winter break, there are n cows that need to attend a party held at the farm numbered x. The farms are connected by m directed roads, each with a certain length. Each cow travels to the party and then returns home along the shortest possible path. Your task is to compute the longest round‐trip time among all cows.

Formally, consider a directed graph with n nodes (numbered from 1 to n) and m directed edges. Each edge from node u to v has a weight w. Let the party be held at node x. For each node i (representing a cow’s home), let d(i, x) be the length of the shortest path from i to x, and d(x, i) be the length of the shortest path from x back to i. You are required to find:

\( \max_{1 \leq i \leq n} \{ d(i, x) + d(x, i) \} \)

It is guaranteed that there is a path from each node to x and from x to each node.

inputFormat

The first line contains three integers n, m, and x (1 ≤ x ≤ n), representing the number of cows (nodes), the number of roads, and the destination (party) node respectively.

Each of the following m lines contains three integers u, v, and w representing a directed road from node u to node v with length w.

outputFormat

Output a single integer which is the longest round-trip time among all cows.

sample

4 8 2
1 2 4
1 3 2
3 2 1
2 4 2
4 2 3
2 1 7
3 4 1
4 3 5

11