A mesh of n sensors (numbered 0 to n-1) is wired by one-way signal links, each taking a positive integer number of milliseconds to carry a ping from its start sensor to its end sensor.
At time 0, sensor s emits a ping. The ping travels along every outgoing link simultaneously, and a sensor is considered to have received the ping the moment the earliest-arriving copy reaches it. Report the time at which the LAST sensor receives the ping (that is, the maximum over all sensors of the earliest arrival time). If at least one sensor never receives the ping, report that the mesh does not fully settle.
Input format
Line 1: three integers n, m, and s.
Each of the next m lines: three integers u v w, a one-way link from sensor u to sensor v taking w milliseconds.
Output format
A single integer: the time when all sensors have received the ping, or -1 if some sensor never does. (If n is 1 the answer is 0.)
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 0 <= s, u, v <= n-1
- 1 <= w <= 1000000