题目描述

FJ打算拓展他的牛奶销售市场。他打算将牛奶销售拓展到编号为1...N的N个城镇(1 <= N <= 25000）。这些城镇通过编号为1..R的R（1 <= R <= 50,000）条道路和(或)编号为1...P的P（1 <= P <= 50,000）条航线相连。每条道路i连接城镇A_i和B_i，花费为C_i。
对于道路0 <= C_i <= 10000，然而航线的花费很奇怪，花费C_i可能是负数(-10000 <= C_i <= 10000)。道路是双向的，可以从A_i到B_i，也可以从B_i到A_i。航线是单向的，只能从A_i到B_i，而且由于航班管控，如果有一条航线从A_i到B_i，那么一定不可能通过一些道路和航线从B_i到A_i。
由于FJ的牛奶很受欢迎，所有的城镇都订购了他的牛奶。他想知道从中心城镇S(1<=S<=N)把牛奶分别送到每个城镇的最低花费。或者知道那是不可能的。

输入格式：

第1行：4个空格分隔的整数N, R, P, S,分别表示城镇的数量，道路的数量，航线的数量和中心城镇的编号。
第2号到第R+1行：每行3个空格分隔的整数A_i, B_i和C_i，描述一条道路信息。
第R+2行到R+P+1行：每行3个空格分隔的整数A_i, B_i和C_i，描述一条航线信息。

输出格式：

共N行，第i行输出从中心城镇S到城镇i的最小花费，如果不能到达，输出"NO PATH"。

输入样例#1：

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

输出样例#1：

NO PATH 
NO PATH 
5 
0 
-95 
-100