原題來自：USACO 2011 Jan. Gold

Farmer John 正在一個(gè)新的銷售區(qū)域?qū)λ呐Ｄ啼N售方案進(jìn)行調(diào)查。他想把牛奶送到 T 個(gè)城鎮(zhèn) ，編號為 1 到 T。這些城鎮(zhèn)之間通過 R 條道路（編號為 1 到 R）和 P 條航線（編號為 1 到 P）連接。每條道路 i 或者航線 i 連接城鎮(zhèn) Ai 到 Bi，花費(fèi)為 Ci 。

對于道路，0≤Ci≤104 ，然而航線的花費(fèi)很神奇，花費(fèi) Ci 可能是負(fù)數(shù)。道路是雙向的，可以從 Ai 到 Bi ，也可以從 Bi 到 Ai ，花費(fèi)都是 Ci 。然而航線與之不同，只可以從 Ai 到 Bi 。

事實(shí)上，由于最近恐怖主義太囂張，為了社會(huì)和諧，出臺(tái)了一些政策保證：如果有一條航線可以從 Ai 到 Bi ，那么保證不可能通過一些道路和航線從 Bi 回到 Ai 。由于 FJ 的奶牛世界公認(rèn)十分給力，他需要運(yùn)送奶牛到每一個(gè)城鎮(zhèn)。他想找到從發(fā)送中心城鎮(zhèn) S 把奶牛送到每個(gè)城鎮(zhèn)的最便宜的方案，或者知道這是不可能的。

第一行為四個(gè)空格隔開的整數(shù)：T,R,P,S；

第二到第 R+1 行：三個(gè)空格隔開的整數(shù)（表示一條道路）：Ai,Bi 和 Ci；

第 R+2 到 R+P+1 行：三個(gè)空格隔開的整數(shù)（表示一條航線）：Ai,Bi 和 Ci 。

輸出 T 行，第 i 行表示到達(dá)城鎮(zhèn) i 的最小花費(fèi)，如果不存在輸出 NO PATH。

樣例說明

一共六個(gè)城鎮(zhèn)。在 1 和 2，3 和 4，5 和 6 之間有道路，花費(fèi)分別是 5,5,10。同時(shí)有三條航線：3→5，4→6 和 1→3，花費(fèi)分別是 ?100,?100,?10。FJ 的中心城鎮(zhèn)在城鎮(zhèn) 4。FJ 的奶牛從 4 號城鎮(zhèn)開始，可以通過道路到達(dá) 3 號城鎮(zhèn)。然后他們會(huì)通過航線達(dá)到 5 和 6 號城鎮(zhèn)。但是不可能到達(dá) 1 和 2 號城鎮(zhèn)。

數(shù)據(jù)范圍：

對于全部數(shù)據(jù)，1≤T≤2.5×10⁴,1≤R,P≤5×10⁴,1≤Ai,Bi,S≤T。保證對于所有道路，0≤Ci≤10⁴,對于所有航線，?10⁴≤Ci≤10⁴ 。

信息學(xué)一本通 圖論