Farmer John正在一个新的销售区域对它的牛奶销售方案进行调查。他想把牛奶送到T个城镇（1≤T≤25000），编号为1~T。这些城镇之间通过R条道路（1≤R≤50000，编号为1到R）和P条航线（1≤P≤50000，编号为1到P）连接。每条道路i或者航线i连接城镇Ai（1≤Ai≤T）到Bi（1≤Bi≤T），花费为Ci。对于道路，0≤Ci≤10000，然而航线的花费很神奇，花费Ci可能是负数（-10000≤Ci≤10000）。道路是双向的，可以从Ai到Bi，也可以从Bi到Ai，花费都是Ci。然而航线与之不同，只可以从Ai到Bi。

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

第一行：4个空格隔开的整数：T,RP,S。

第2到R+1行：3个空格隔开的整数（表示一条道路）：Ai,Bi和Ci。

第R+2行到R+P+1行：3个空格隔开的整数（表示一条航线）：Ai，Bi和Ci。

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

【样例输入解释】

一共6个城镇。在1-2,3-4,5-6之间有道路，花费分别是5,5,10。同时有3条航线：3->5,4->6和1->3，花费分别是-100，-100，-10。Farmer John的中心城镇在城镇4。

【样例输出解释】

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

一本通提高