时间限制：1秒　　内存限制：256M

---

【题目描述】

　　CQ市有 \(n\) 个小镇，编号为 \(1..n\)，有 \(m\) 条双向公路和和 \(k\) 条单向的水运航线连接。

　　其中第i条双公路连接小镇 \(a_i\) 和 \(b_i\)，通行费为 \(c_i\)，其中 \(0 ≤ c_i ≤ 10,000\)；而第 \(j\) 条单向水运航线能从小镇 \(u_i\) 到 \(v_i\)，通行费用为 \(t_i\)，由于水运有市政府补贴，水运行线的费用可能为负数，即\( -10,000 ≤ t_i ≤ 10,000\)。注意，如果有一条水运航线可以从 \(a_i\) 到 \(b_i\)，那么保证不可能通过一些公路和航线从 \(b_i\) 回到 \(a_i\)。

　　现在请你找到从CQ市的沙坪坝镇 \(s(1 ≤ s ≤ n)\) 把到每个小镇的最便宜的方案，或者知道这是不可能的。

【输入格式】

　　第一行有四个空格隔开的整数: \(n, m, k\) 和 \(s\)。
　　接下来的 \(m\) 行，每行包含三个空格隔开的整数（表示一条公路）：\(a_i, b_i\) 和 \(c_i\)。
　　再接下来 \(k\) 行，每行包含三个空格隔开的整数（表示一条水运线）：\(u_i, v_i\) 和 \(t_i\)。

【输出格式】

　　输出 \(n\) 行：从 \(s\) 到达小镇 \(i\) 的最小花费，如果不存在输出 "NO PATH"。

【输入输出样例】

　Input

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

　Output

NO PATH
NO PATH
5
0
-95
-100

【输入输出样例解释】

　　一共六个小镇。在 1-2，3-4，5-6 之间有公路，花费分别是 5，5，10。同时有三条水运线：3->5，4->6和1->3，花费分别是 -100，-100，-10。沙坪坝小镇为 4。从 4 号小镇开始，可以通过公路到达 3 号小镇。然后他们会通过水运航线到达到 5 和 6 号小镇。但是不可能到达 1 和 2 号小镇。

【数据限制】

　　对于 \(100\%\) 的数据，\(1 ≤ n ≤ 25,000\)，\(1 ≤ m,k ≤ 50,000\)。

【来源】

　　Mr.he