P17639 [ICPC 2019 Yinchuan R] Delivery Route

小马是一家快递公司的老板。公司需要将包裹送达 $n$ 个办公室，办公室编号从 $1$ 到 $n$。特别地，第 $s$ 个办公室是这家快递公司的转运站。 这些办公室之间共有 $x$ 条普通的双向道路和 $y$ 条单向道路。如果快递车经过第 $i$ 条道路，将会消耗 $c_i$ 的能量。通常情况下，在一条道路上消耗的能量必须是非负的。然而，得益于实验性的充电轨道，某些单向道路上的消耗值可能为负。 除此之外，小马还获得了以下公开信息。有关部门承诺，如果存在一条从 $a_i$ 到 $b_i$ 的单向道路，则不可能从 $b_i$ 返回 $a_i$。 为了避免快递车在路上抛锚，小刀想要找出从转运站到这些办公室的最低能量消耗。

第一行包含四个整数 $n~(1 \le n \le 25000)$、$x, y~(1 \le x, y \le 50000)$ 和 $s~(1 \le s \le n)$。接下来共有 $x+y$ 行，每行包含三个整数 $a_i, b_i~(1 \le a_i, b_i \le n, a_i \neq b_i)$ 和 $c_i~(-10000 \le c_i \le 10000)$，描述各条道路。所给的前 $x$ 条道路是普通的双向道路，后 $y$ 条道路是单向道路。

输出应包含 $n$ 行，第 $i$ 行表示从第 $s$ 个办公室到达第 $i$ 个办公室的最小能量消耗（如果可能），若无法到达第 $i$ 个办公室，则输出 `NO PATH`。

翻译由 DeepSeek V4 Pro 完成