410436: GYM104021 H Delivery Route

Pony is the boss of a courier company. The company needs to deliver packages to $$$n$$$ offices numbered from $$$1$$$ to $$$n$$$. Especially, the $$$s$$$-th office is the transfer station of the courier company.

There are $$$x$$$ ordinary two-way roads and $$$y$$$ one-way roads between these offices. The delivery vans will consume $$$c_i$$$ power if they pass through the $$$i$$$-th road. In general, the power consumption on one road must be non-negative. However, thanks to the experimental charging rail, the consumption may be negative on some one-way roads.

Besides, Pony got the following public information. The relevant department promised that if there is a one-way street from $$$a_i$$$ to $$$b_i$$$, it is impossible to return from $$$b_i$$$ to $$$a_i$$$.

To avoid the delivery vans anchoring on the road, Xiaodao wants to find these lowest power consumptions from the transfer station to these offices.

The first line contains four integers $$$n~(1 \le n \le 25000), x, y~(1 \le x, y \le 50000)$$$, and $$$s~(1 \le s \le n)$$$. This is followed by $$$x+y$$$ lines, each line of which contains three integer $$$a_i, b_i~(1 \le a_i, b_i \le n, a_i \neq b_i)$$$ and $$$c_i~(-10000 \le c_i \le 10000)$$$ describing the roads. The first $$$x$$$ given roads are ordinary two-way roads, and the last $$$y$$$ given roads are one-way roads.

The output should contain $$$n$$$ lines, the $$$i$$$-th line represents the minimum energy consumption from $$$s$$$-th to the $$$i$$$-th office if possible, or output "NO PATH" if it is impossible to reach the $$$i$$$-th office.

6 3 3 4
1 2 5
3 4 5
5 6 10
3 5 -100
4 6 -100
1 3 -10

NO PATH
NO PATH
5
0
-95
-100