A survey network has n beacons (numbered 0 to n-1) linked by one-way cables. Each cable carries a signal from its start beacon to its end beacon at a positive integer cost.
Starting from beacon s, a beacon is said to be within budget if the minimum total cost to reach it from s is at most B. The source s itself is within budget (its cost is 0, and B >= 0). Count how many beacons are within budget.
Input format
Line 1: four integers n, m, s, and B.
Each of the next m lines: three integers u v w, a one-way cable from beacon u to beacon v with cost w.
Output format
A single integer: the number of beacons (including s) whose shortest cost from s is at most B.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 0 <= s, u, v <= n-1
- 0 <= B <= 1000000000
- 1 <= w <= 1000000