好的，这是整理好的完整题目描述，包含样例解释：

题目描述

农夫约翰在新的销售区域调查牛奶销售方案。
他要把牛奶送到 $T$ 个城镇，编号为 $1$ 到 $T$。

这些城镇之间通过 $R$ 条道路和 $P$ 条航线连接。

• 每条道路 $i$ 连接 $A_i$ 和 $B_i$，花费 $C_i$（$0 \le C_i \le 10000$），并且是双向的。
• 每条航线 $i$ 连接 $A_i$ 到 $B_i$，花费 $C_i$（$-10000 \le C_i \le 10000$），并且是单向的。

一个重要的政策保证：
如果有一条航线从 $A_i$ 到 $B_i$，那么不可能通过一系列道路和航线从 $B_i$ 回到 $A_i$。
这意味着，航线不会在道路构成的连通分量内形成环，可以认为航线连接不同的“块”，并且有向边只能从某个块指向另一个块，不会反向可达。

约翰需要从发送中心 $S$ 运送奶牛到每个城镇。
请你计算从 $S$ 到每个城镇的最小花费。如果不可达，则输出 NO PATH。

输入格式

第一行四个整数 $T, R, P, S$，分别表示城镇数、道路数、航线数、起点编号。
接下来 $R$ 行，每行三个整数 $A_i, B_i, C_i$，表示一条双向道路及其费用。
接下来 $P$ 行，每行三个整数 $A_i, B_i, C_i$，表示一条单向航线及其费用。

输出格式

输出 $T$ 行，第 $i$ 行表示从 $S$ 到城镇 $i$ 的最小花费，如果不可达则输出 NO PATH。

数据范围

• $1 \le T \le 25000$
• $1 \le R, P \le 50000$
• $1 \le A_i, B_i, S \le T$

输入样例

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

样例解释

城镇数 $T=6$，道路数 $R=3$，航线数 $P=3$，起点 $S=4$。

道路（双向）：

1. 1 ↔ 2，花费 5
2. 3 ↔ 4，花费 5
3. 5 ↔ 6，花费 10

由道路连接关系可得连通分量（块）：

• 块1：城镇 {1, 2}
• 块2：城镇 {3, 4}
• 块3：城镇 {5, 6}

航线（单向）：

1. 3 → 5，花费 -100
2. 4 → 6，花费 -100
3. 1 → 3，花费 -10

航线连接：

• 从块2（城镇 3 或 4）到块3（城镇 5 或 6）
• 从块1（城镇 1 或 2）到块2（城镇 3 或 4）

起点 S = 4（在块2）。

计算到每个城镇的最短路：

• 到城镇 1：从 4 到 1 不可达（没有航线或道路从块2到块1，且块2和块1不直接相连，道路只连接块内）。
  输出 NO PATH。
• 到城镇 2：同理不可达，输出 NO PATH。
• 到城镇 3：在同一个块2内，通过道路 3↔4 花费 5，从 4 到 3 最短花费 5。
  输出 5。
• 到城镇 4：起点自身，花费 0。
  输出 0。
• 到城镇 5：可以从 4 走航线 4→6 花费 -100 到达 6（在块3），再通过道路 6↔5 花费 10，总花费 -100+10 = -90？
  等一下，还有别的路线：4→3（花费 5）然后 3→5（花费 -100），总花费 5 + (-100) = -95。
  比较两条路：
  1. 4→6（-100）→5（+10） = -90
  2. 4→3（+5）→5（-100） = -95
     更优的是 -95。
     所以输出 -95。
• 到城镇 6：
  4→6 直接航线花费 -100，所以输出 -100。

最终输出：

NO PATH
NO PATH
5
0
-95
-100