分数: 500 点
问题陈述
有 N 城市编号 1 to N,通过连接 M 铁路。
您现在位于城市 1,与 10^{100} 金币和 S 银币在你的口袋里。
的 i-th铁路连接城市 U_i 和城市 V_i 双向,单程旅行费用 A_i 银币和需要 B_i 分钟。 您不能使用金币支付车费。
每个城市都有兑换柜台。在 City 的兑换柜台 i,可以得到 C_i 银币 1 金币。 交易需要 您给予的每枚金币都需要 D_i 分钟。 您可以在每个兑换柜台兑换任意数量的金币。
对于每个 t=2, ..., N,求从 City 出发所需的最短时间 1 前往城市 t。您可以忽略等待火车的时间。
约束
- 2 \leq N \leq 50
- N-1 \leq M \leq 100
- 0 \leq S \leq 10^9
- 1 \leq A_i \leq 50
- 1 \leq B_i,C_i,D_i \leq 10^9
- 1 \leq U_i < V_i \leq N
- 没有对 i, j(i \neq j) 这样 (U_i,V_i)=(U_j,V_j).
- 各城市 从城市可以到达 t=2,...,N 从市区可到达 1 拥有一定数量的铁路。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M S U_1 V_1 A_1 B_1 : U_M V_M A_M B_M C_1 D_1 : C_N D_N
输出
对于每个 t=2, ..., N 按照此顺序,打印一行,其中包含从 City 出发所需的最短时间 1 前往城市 t.
示例输入 1
3 2 1 1 2 1 2 1 3 2 4 1 11 1 2 2 5
示例输出 1
2 14
本输入中的铁路网如下图所示。
在此图中,每个城市的标记如下:
- 第一行:身份证号码 i 的城市 (i 城市 i)
- 第二行: C_i / D_i
同样,每条铁路的标签如下:
- 第一行:身份证号码 i 铁路(i 为 i输入中的第 条铁路)
- 第二行: A_i / B_i

您可以从城市出发 1 前往城市 2 in 2 分钟,如下:
- 使用 1-st 铁路将从城市搬迁 1 前往城市 2 in 2 分钟。
您可以从城市出发 1 前往城市 3 in 14 分钟,如下:
- 使用 1-st 铁路将从城市搬迁 1 前往城市 2 in 2 分钟。
- 在城市兑换柜台 2, 交换 3 金币 3 银币 6 分钟。
- 使用 1-st 铁路将从城市搬迁 2 前往城市 1 in 2 分钟。
- 使用 2-nd 铁路将从城市迁出 1 前往城市 3 in 4 分钟。
示例输入 2
4 4 1 1 2 1 5 1 3 4 4 2 4 2 2 3 4 1 1 3 1 3 1 5 2 6 4
示例输出 2
5 5 7
本次输入的铁路网如下图所示:

您可以从城市出发 1 前往城市 4 in 7 分钟,如下:
- 在城市兑换柜台 1, 交换 2 金币 6 银币 2 分钟。
- 使用 2-nd 铁路将从城市迁出 1 前往城市 3 in 4 分钟。
- 使用 4第 条铁路将从城市迁出 3 前往城市 4 in 1 分钟。
示例输入 3
6 5 1 1 2 1 1 1 3 2 1 2 4 5 1 3 5 11 1 1 6 50 1 1 10000 1 3000 1 700 1 100 1 1 100 1
示例输出 3
1 9003 14606 16510 16576
本次输入的铁路网如下图所示:

您可以从城市出发 1 前往城市 6 in 16576 分钟,如下:
- 使用 1-st 铁路将从城市搬迁 1 前往城市 2 in 1 分钟。
- 在城市兑换柜台 2, 交换 3 金币 3 银币 9000 分钟。
- 使用 1-st 铁路将从城市搬迁 2 前往城市 1 in 1 分钟。
- 使用 2-nd 铁路将从城市迁出 1 前往城市 3 in 1 分钟。
- 在城市兑换柜台 3, 交换 8 金币 8 银币 5600 分钟。
- 使用 2-nd 铁路将从城市迁出 3 前往城市 1 in 1 分钟。
- 使用 1-st 铁路将从城市搬迁 1 前往城市 2 in 1 分钟。
- 使用 3-rd铁路将从城市迁出 2 前往城市 4 in 1 分钟。
- 在城市兑换柜台 4, 交换 19 金币 19 银币 1900 分钟。
- 使用 3-rd铁路将从城市迁出 4 前往城市 2 in 1 分钟。
- 使用 1-st 铁路将从城市搬迁 2 前往城市 1 in 1 分钟。
- 使用 2-nd 铁路将从城市迁出 1 前往城市 3 in 1 分钟。
- 使用 4第 条铁路将从城市迁出 3 前往城市 5 in 1 分钟。
- 在城市兑换柜台 5, 交换 63 金币 63 银币 63 分钟。
- 使用 4第 条铁路将从城市迁出 5 前往城市 3 in 1 分钟。
- 使用 2-nd 铁路将从城市迁出 3 前往城市 1 in 1 分钟。
- 使用 5第 条铁路将从城市迁出 1 前往城市 6 in 1 分钟。
示例输入 4
4 6 1000000000 1 2 50 1 1 3 50 5 1 4 50 7 2 3 50 2 2 4 50 4 3 4 50 3 10 2 4 4 5 5 7 7
示例输出 4
1 3 5
本次输入的铁路网如下图所示:

示例输入 5
2 1 0 1 2 1 1 1 1000000000 1 1
示例输出 5
1000000001
本次输入的铁路网如下图所示:

您可以从城市出发 1 前往城市 2 in 1000000001 分钟,如下:
- 在城市兑换柜台 1, 交换 1 金币 1 银币 1000000000 分钟。
- 使用 1-st 铁路将从城市搬迁 1 前往城市 2 in 1 分钟。