33OJ
登录 注册

#P17639. [ICPC 2019 Yinchuan R] Delivery Route

[ICPC 2019 Yinchuan R] Delivery Route

Problem Description

Pony is the boss of a courier company. The company needs to deliver packages to nn offices numbered from 11 to nn. Especially, the ss-th office is the transfer station of the courier company.

There are xx ordinary two-way roads and yy one-way roads between these offices. The delivery vans will consume cic_i power if they pass through the ii-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 aia_i to bib_i, it is impossible to return from bib_i to aia_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.

Input Format

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

Output Format

The output should contain nn lines, the ii-th line represents the minimum energy consumption from ss-th to the ii-th office if possible, or output NO PATH if it is impossible to reach the ii-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