農(nóng)夫約翰正在針對(duì)一個(gè)新區(qū)域的牛奶配送合同進(jìn)行研究。他打算分發(fā)牛奶到T個(gè)城鎮(zhèn)（標(biāo)號(hào)為1..T），這些城鎮(zhèn)通過(guò)R條標(biāo)號(hào)為（1..R）的道路和P條標(biāo)號(hào)為（1..P）的航路相連。

每一條公路i或者航路i表示成連接城鎮(zhèn)Ai（1<=A_i<=T）和Bi（1<=Bi<=T）代價(jià)為Ci。每一條公路，Ci的范圍為0<=Ci<=10,000；由于奇怪的運(yùn)營(yíng)策略，每一條航路的Ci可能為負(fù)的，也就是-10,000<=Ci<=10,000。

每一條公路都是雙向的，正向和反向的花費(fèi)是一樣的，都是非負(fù)的。

每一條航路都根據(jù)輸入的Ai和Bi進(jìn)行從Ai->Bi的單向通行。實(shí)際上，如果現(xiàn)在有一條航路是從Ai到Bi的話，那么意味著肯定沒(méi)有通行方案從Bi回到Ai。

農(nóng)夫約翰想把他那優(yōu)良的牛奶從配送中心送到各個(gè)城鎮(zhèn)，當(dāng)然希望代價(jià)越小越好，你可以幫助他嘛？配送中心位于城鎮(zhèn)S中（1<=S<=T）。

輸入的第一行包含四個(gè)用空格隔開(kāi)的整數(shù)T，R，P，S。

接下來(lái)R行，描述公路信息，每行包含三個(gè)整數(shù)，分別表示Ai，Bi和Ci。

接下來(lái)P行，描述航路信息，每行包含三個(gè)整數(shù)，分別表示Ai，Bi和Ci。

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