7# 题目背景

小王在忙，看泠鸢yousa直播，请你帮他送一下牛奶嘿嘿嘿

题目描述

农夫小王正在针对一个新区域的牛奶配送合同进行研究。他打算分发牛奶到T个城镇（标号为1 ~ T），这些城镇通过R条标号为（1 ~ R）的道路和P条标号为（1~ P）的航路相连。

每一条公路i或者航路i表示成连接城镇$A_i$​（1<=$A_i$<=T）和$B_i$（1<=$B_i$<=T）代价为$C​_i$​。每一条公路，$C​_i$​的范围为0<=$C​_i$​​<=10,000；由于奇怪的运营策略，每一条航路的$C​_i$​可能为负的，也就是-10,000<=$C​_i$​​<=10,000。

每一条公路都是双向的，正向和反向的花费是一样的，都是非负的。

每一条航路都根据输入的$A_i$​和$B_i$进行从$A_i$​->$B_i$的单向通行。实际上，如果现在有一条航路是从$A_i$​到$B_i$的话，那么意味着肯定没有通行方案从$B_i$回到$A_i$​​。

农夫小王想把他那优良的牛奶从配送中心送到各个城镇，当然希望代价越小越好，你可以帮助他嘛？配送中心位于城镇S中（1<=S<=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