Description

快递公司打算用新型电动汽车将包裹送至编号为 1 至 n 的 n 个地点。地点 s 为配送起点。

这些地点之间有 x 条双向道路，第 i 条双向道路连接地点 xi 和 yi ,通过需要消耗一个非负整数值的能量 ci。同时该公司与运输部门合作试验性地建了 y 条可充电道路！这些可充电道路都是单向的，第 j 条单向道路从地点 xj 到 yj ，消耗的能量 ci 可能为负整数,也可能为非负整数。

但是，由于某些原因，这个运输网络有个限制：对于任意一条从 aj 到 bj 的单向道路 j ，整个运输网络中不存在一条路径能从 bj 再回到 aj 。

现在快递公司希望你能回答：从配送起点 s 到每一个地点的最小能量消耗（可能为负数）分别是多少？

Format

Input

第一行四个正整数 n(1 ≤ n ≤ 50000),x,y(1 ≤ x,y ≤ 500000),s(1 ≤ s ≤ n) 表示有 n 个地点， x 条双向道路和 y 条单向道路，起点为 s

接下来 (x+y) 行，每行三个整数 ai,bi(1 ≤ ai,bi ≤ n,ai!=bi),ci(-10000 ≤ ci ≤ 10000) ，描述一条道路。前 x 条道路为双向的，后 y 条为单向的。

Output

n 行，第 i 行，若从起点 s 到达到 i ，则输出一个整数表示从起点 s 到 i 的最少能量消耗，否则输出 NO PATH

Samples

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

输入 #2 见数据包 输出 #2 见数据包

样例解释 样例 #1 起点到各个点的最少能量消耗的路径分别为： 1，2：无法到达；

3：4 —>3;

5：4 —>3—>5;

6：4 —>6;

Limitation

测试点编号n≤ x,y≤ 特殊约定

1,2 50000 500000 ci>0

3,4 5000 50000 无

5~10 50000 500000 无

对于所有测试点， 均有1 ≤ n ≤ 50000,1 ≤ x, y ≤ 500000, -10000 ≤ ci ≤ 10000