农夫约翰正在针对一个新区域的牛奶配送合同进行研究。他打算分发牛奶到 T 个城镇（标号为1 \dots T），这些城镇通过 R 条标号为（1 \dots R）的道路和 P 条标号为（1 \dots P）的航路相连。
每一条公路 i 或者航路 i 表示成连接城镇 A_i（1 \le A_i \le T）和 B_i（1 \le B_i \le T）代价为C_i 。每一条公路，C_i 的范围为 0 \le C_i \le 10,000 ；由于奇怪的运营策略，每一条航路的 C_i 可能为负的，也就是 -10,000 \le C_i \le 10,000。
每一条公路都是双向的，正向和反向的花费是一样的，都是非负的。
每一条航路都根据输入的 A_i 和 B_i 进行从 A_i -> B_i 的单向通行。实际上，如果现在有一条航路是从 A_i 到 B_i 的话，那么意味着肯定没有任何通行方案从 B_i 回到 A_i。
农夫约翰想把他那优良的牛奶从配送中心送到各个城镇，当然希望代价越小越好，你可以帮助他嘛？配送中心位于城镇 S 中（1 \le S \le T）。
输入的第一行包含四个用空格隔开的整数T,R,P,S。
接下来 R 行，描述公路信息，每行包含三个整数，分别表示A_i ， B_i 和 C_i。
接下来P行，描述航路信息，每行包含三个整数，分别表示A_i ， B_i 和 C_i。
输出 T 行，分别表示从城镇 S 到每个城市的最小花费，如果到不了的话输出 NO PATH。
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
【数据规模】
对于 20\% 的数据，T \le 100，R \le 500，P \le 500；
对于 30\% 的数据，R \le 1000，R \le 10000，P \le 3000；
对于 100\% 的数据，1 \le T \le 25000，1 \le R \le 50000，1 \le P \le 50000。