Party

There are N villages numbered from 1 to N, and one student lives in each village.

One day, all students decide to gather in village X for a party. There are M directed roads between the villages, and each road has a given travel time.

Each student must travel from their own village to village X, then return home after the party. They want to minimize their travel time in each direction.

Because the roads are directed, the shortest path to the party and the shortest path back home may be different. Find the largest shortest round-trip time among all students.

The first line contains three integers N, M, and X, separated by spaces.

• 1 <= N <= 1,000
• 1 <= M <= 10,000
• 1 <= X <= N

Each of the next M lines contains three integers A, B, and T, meaning there is a directed road from village A to village B that takes T time.

• 1 <= T <= 100
• No road starts and ends at the same village.
• For the same ordered pair of start and end villages, there is at most one road.

The input only contains cases where every student can reach village X from home and can return home from village X.

Print the largest shortest round-trip time needed by any student to go between their village and village X.