A logistics company runs n sorting hubs (numbered 0 to n-1) connected by one-way conveyor links. Each link goes from one hub to another and takes a positive integer number of minutes.
Given a source hub s, compute, for every hub, the minimum number of minutes to reach it from s following links in their allowed direction. A hub that cannot be reached from s has no finite distance.
Input format
Line 1: three integers n, m, and s (the number of hubs, the number of links, and the source hub).
Each of the next m lines: three integers u v w, a one-way link from hub u to hub v taking w minutes.
Output format
One line with n space-separated tokens. Token i is the shortest distance from s to hub i, or the literal INF if hub i is unreachable. (The distance from s to itself is 0.)
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 0 <= s, u, v <= n-1
- 1 <= w <= 1000000