Pony 是一家快递公司的老板。公司需要向编号为 $1$ 到 $n$ 的 $n$ 个办公室运送包裹。其中，第 $s$ 个办公室是快递公司的中转站。

这些办公室之间有 $x$ 条普通的双向道路和 $y$ 条单向道路。货车通过第 $i$ 条道路时会消耗 $c_i$ 的能量。通常情况下，道路的能量消耗必须是非负的。然而，得益于实验性的充电轨道，某些单向道路的消耗可能是负数。

此外，Pony 获得了以下公开信息：相关部门承诺，如果存在一条从 $a_i$ 到 $b_i$ 的单向道路，那么就不可能从 $b_i$ 返回到 $a_i$。

为了避免货车在路上抛锚，Xiaodao 想要找出从中转站到这些办公室的最低能量消耗。

输入格式

第一行包含四个整数 $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”。

样例

输入 1

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

输出 1

NO PATH
NO PATH
5
0
-95
-100