题目描述

$\red{Farmer John}$正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到$\red{T}$个城镇 $\red{(1 <= T <= 25,000)，}$编号为$\red{1T}$。这些城镇之间通过$\red{R}$条道路 $\red{(1 <= R <= 50,000，}$编号为$\red{1}$到$\red{R) }$和$\red{P}$条航线 $\red{(1 <= P <= 50,000，}$编号为$\red{1}$到$\red{P) }$连接。

每条道路$\red{i}$或者航线$\red{i}$连接城镇$\red{A_i (1 <= A_i <= T)}$到$\red{B_i (1 <= B_i <= T)，}$花费为$\red{C_i}$。对于道路，$\red{0 <= C_i <= 10,000}$; 然而航线的花费很神奇，花费$\red{C_i}$可能是负数$\red{(-10,000 <= C_i <= 10,000)}$。道路是双向的，可以从$\red{A_i}$到$\red{B_i，}$也可以从$\red{B_i}$到$\red{A_i，}$花费都是$\red{C_i}$。然而航线与之不同，只可以从$\red{A_i}$到$\red{B_i}$。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台 了一些政策保证：如果有一条航线可以从$\red{A_i}$到$\red{B_i，}$那么保证不可能通过一些道路和航线从$\red{B_i}$回到$\red{A_i}$。由于$\red{FJ}$的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇$\red{S(1 <= S <= T) }$把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

输入格式

第$\red{1}$行：四个空格隔开的整数: $\red{T, R, P, }$和$\red{S }$

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

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

输出格式

第$\red{1}$到$\red{T}$行：从$\red{S}$到达城镇$\red{i}$的最小花费，如果不存在输出"$\red{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

提示

样例输入解释：

一共六个城镇。在$\red{1-2，}$$\red{3-4，}$$\red{5-6}$之间有道路，花费分别是$\red{5，}$$\red{5，}$$\red{10}$。同时有三条航线：$\red{3->5，}$ $\red{4->6}$和$\red{1->3，}$花费分别是$\red{-100，}$$\red{-100，}$$\red{-10}$。$\red{FJ}$的中心城镇在城镇$\red{4}$。

样例输出解释：

$\red{FJ}$的奶牛从$\red{4}$号城镇开始，可以通过道路到达$\red{3}$号城镇。然后他们会通过航线达到$\red{5}$和$\red{6}$号城镇。 但是不可能到达$\red{1}$和$\red{2}$号城镇。