AT_soundhound2018_summer_qual_d Saving Snuuk

kenkoooo 正在计划在すぬけ国旅行。すぬけ国有 $n$ 个城市，$m$ 条火车线路。城市编号为 $1$ 到 $n$，第 $i$ 条火车连接城市 $u_i$ 和 $v_i$，且可以双向通行。通过换乘火车，可以从任意城市到达任意其他城市。 すぬけ国有两种货币：日元和スヌーク。每条火车的票价可以用任意一种货币支付，第 $i$ 条火车用日元支付为 $a_i$ 日元，用スヌーク支付为 $b_i$ スヌーク。 每个城市都有兑换所，可以将所有持有的日元以 $1:1$ 的比例兑换成スヌーク。但兑换时必须将所有日元一次性兑换成スヌーク。例如，若 kenkoooo 持有 $X$ 日元，兑换后将持有 $X$ スヌーク。当前所有城市都有兑换所，但第 $i$ 个城市的兑换所将在 $i$ 年后关闭，$i$ 年后及之后无法再使用。 kenkoooo 持有 $10^{15}$ 日元，从城市 $s$ 出发前往城市 $t$。途中可以在任意有兑换所的城市将日元兑换成スヌーク。可以在城市 $s$ 或 $t$ 的兑换所进行兑换。 kenkoooo 想通过合理选择路线和兑换城市，使得到达城市 $t$ 时持有的スヌーク数量最大。请对于 $i=0,\ldots,n-1$，求出 $i$ 年后从城市 $s$ 到城市 $t$ 时，kenkoooo 能持有的最大スヌーク数量。注意，旅行过程中不会跨年。

输入通过标准输入给出，格式如下： > $n$ $m$ $s$ $t$ > $u_1$ $v_1$ $a_1$ $b_1$ > $\vdots$ > $u_m$ $v_m$ $a_m$ $b_m$

输出 $n$ 行。第 $i$ 行输出 $i-1$ 年后从城市 $s$ 到城市 $t$ 时，kenkoooo 能持有的最大スヌーク数量。

## 限制条件 - $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$ - 当 $i \neq j$ 时，$u_i \neq u_j$ 或 $v_i \neq v_j$ - 任意城市之间都可以通过火车换乘到达 - 所有输入均为整数 ## 样例解释 1 $0$ 年后，在城市 $1$ 兑换最优。$1$ 年后，在城市 $2$ 兑换最优。即使兑换所关闭，仍然可以访问城市 $1$。注意，兑换时必须将所有日元一次性兑换成スヌーク，不能只兑换部分。$2$ 年后，在城市 $3$ 兑换最优。$3$ 年后，在城市 $4$ 兑换最优。可以多次使用同一条火车线路。 由 ChatGPT 4.1 翻译