分数: 400 点
问题陈述
Kenkoooo 计划在 斯努克共和国 旅行。 在这个国家,有 n 城市和 m 火车运行。 城市已编号 1 通过 n,以及 i第趟列车连接城市 u_i 和 v_i 双向。 从任何城市换乘火车都可以到达任何城市。
该国使用两种货币:日元和斯努克。 任何火车票价都可以用日元和斯努克支付。 票价为 i第趟列车是 a_i 日元(如果以日元支付),以及 b_i snuuk(如果以 snuuk 支付)。
在设有货币兑换处的城市,您可以兑换 1 日元成 1 斯努克。 然而,当你进行货币兑换时,你必须将所有日元兑换成斯努克。 也就是说,如果 Kenkoooo 在他有钱时进行货币兑换 X 日元,他就会有 X 斯努克。 目前,每个城市都有货币兑换处,但位于城市的办事处 i 将在以下时间关闭 i 年,并且该年及之后永远不能使用。
Kenkoooo 计划离开城市 s 与 10^{15} 口袋里有日元,前往城市 t,并在旅行时在某个城市将日元兑换成斯努克。 可以在市内兑换 s 或城市 t.
Kenkoooo 希望在到达曼城时能有尽可能多的 snuuk t 通过对出行路线和城市进行最优选择进行交换。 对于每个 i=0,...,n-1,求 Kenkoooo 到达 City 时拥有的最大 snuuk 数量 t 如果他从城市出发旅行 s 前往城市 t 之后 i 年。 您可以假设旅行将在年内完成。
约束
- 2 \leq n \leq 10^5
- 1 \leq m \leq 10^5
- 1 \leq s,t \leq n
- s \neq t
- 1 \leq u_i < v_i \leq n
- 1 \leq a_i,b_i \leq 10^9
- If i\neq j,那么 u_i \neq u_j or v_i \neq v_j.
- 从任何城市换乘火车都可以到达任何城市。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
n m s t u_1 v_1 a_1 b_1 : u_m v_m a_m b_m
输出
打印 n 行。 在 i第行,打印 Kenkoooo 到达 City 时拥有的最大 snuuk 数量 t 如果他从城市出发旅行 s 前往城市 t 之后 i-1 年。
示例输入 1
4 3 2 3 1 4 1 100 1 2 1 10 1 3 20 1
示例输出 1
999999999999998 999999999999989 999999999999979 999999999999897
之后 0 年,最好在城市进行交换 1.
之后 1 年,最好在城市进行交换 2.
请注意城市
即使兑换处关闭后,仍然可以访问 1 。
另请注意,如果允许保留 1 日元什么时候在市内兑换 2 把剩下的日元换成snuuk,就可以到达City了 3 与 999999999999998 snuuk,但这是不允许的。
之后 2 年,最好在城市进行交换 3.
之后 3 年,最好在城市进行交换 4。
请注意,同一列火车可以多次使用。
示例输入 2
8 12 3 8 2 8 685087149 857180777 6 7 298270585 209942236 2 4 346080035 234079976 2 5 131857300 22507157 4 8 30723332 173476334 2 6 480845267 448565596 1 4 181424400 548830121 4 5 57429995 195056405 7 8 160277628 479932440 1 6 475692952 203530153 3 5 336869679 160714712 2 7 389775999 199123879
示例输出 2
999999574976994 999999574976994 999999574976994 999999574976994 999999574976994 999999574976994 999999574976994 999999574976994