题目描述

Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到$T$个城镇 ，编号为$1 \sim T$。这些城镇之间通过$R$条道路 (编号为$1$到$R$) 和$P$条航线 (编号为$1$到$P$) 连接。

每条道路$i$或者航线$i$连接城镇$A_i$ 到$B_i$，花费为$C_i$。对于道路，$0 <= C_i <= 10,000$;然而航线的花费很神奇，花费$C_i$可能是负数$(-10,000 <= C_i <= 10,000)$。道路是双向的，可以从$A_i$到$B_i$，也可以从$B_i$到$A_i$，花费都是$C_i$。然而航线与之不同，只可以从$A_i$到$B_i$。事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台 了一些政策保证：如果有一条航线可以从$A_i$到$B_i$，那么保证不可能通过一些道路和航线从$B_i$回到$A_i$。由于FJ的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇$S$ 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

输入

第1行：四个空格隔开的整数: T, R, P, and S

第$2$到$R+1$行：三个空格隔开的整数（表示一条道路）：$A_i, B_i 和 C_i$

第$R+2$到$R+P+1$行：三个空格隔开的整数（表示一条航线）：$A_i, B_i$ 和 $C_i$

输出

第$1$到$T$行：从$S$到达城镇$i$的最小花费，如果不存在输出NO PATH。

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

样例输入解释

一共六个城镇。在1-2，3-4，5-6之间有道路，花费分别是5，5，10。

同时有三条航线：3->5， 4->6和1->3，花费分别是-100，-100，-10。

FJ的中心城镇在城镇4。

NO PATH
NO PATH
5
0
-95
-100

样例输出解释

样例输出解释： FJ的奶牛从4号城镇开始，可以通过道路到达3号城镇。

然后他们会通过航线达到5和6号城镇。

但是不可能到达1和2号城镇。

提示

$(1 <= T <= 25,000)$

$1 <= R <= 50,000$

$1 <= P <= 50,000$

$(1 <= A_i <= T)$

$(1 <= B_i <= T)$

$(1 <= S <= T)$