问题描述

有 $N$ 个编号为 $1$ 到 $N$ 的城市，由 $M$ 条铁路连接。

你现在在城市 $1$，口袋里有 $10^{100}$ 个金币和 $S$ 个银币。

第 $i$ 条铁路双向连接城市 $U_i$ 和城市 $V_i$，单程需支付 $A_i$ 个银币并花费 $B_i$ 分钟，不能用金币支付车费。

每个城市都设有兑换柜台。在第 $i$ 个城市的兑换柜台，你可以用 $1$ 个金币换取 $C_i$ 个银币。每兑换 $1$ 个金币需要花费 $D_i$ 分钟。你可以在每个兑换柜台兑换任意数量的金币。

对于每个 $t=2, ..., N$，找到从城市 $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$，输出一行包含从城市 $1$ 到城市 $t$ 的最短时间。

示例输入1

3 2 1
1 2 1 2
1 3 2 4
1 11
1 2
2 5

示例输出1

2
14

这个输入中的铁路网络如下图所示。

在这个图中，每个城市如下标识：

• 第一行：城市的 ID 编号 $i$（城市 $i$ 对应的是 $i$）
• 第二行：$C_i$ / $D_i$

同样，每条铁路如下标识：

• 第一行：铁路的 ID 编号 $i$（输入中的第 $i$ 条铁路对应的是 $i$）
• 第二行：$A_i$ / $B_i$

你可以在 $2$ 分钟内从城市 $1$ 前往城市 $2$，具体操作如下：

• 使用第 $1$ 条铁路，在 $2$ 分钟内从城市 $1$ 前往城市 $2$。

你可以在 $14$ 分钟内从城市 $1$ 前往城市 $3$，具体操作如下：

• 使用第 $1$ 条铁路，在 $2$ 分钟内从城市 $1$ 前往城市 $2$。
• 在城市 $2$ 的兑换柜台中，使用 $3$ 个金币，在 $6$ 分钟内换取 $3$ 个银币。
• 使用第 $1$ 条铁路，在 $2$ 分钟内从城市 $2$ 前往城市 $1$。
• 使用第 $2$ 条铁路，在 $4$ 分钟内从城市 $1$ 前往城市 $3$。

示例输入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

这个输入中的铁路网络如下图所示：

你可以在 $7$ 分钟内从城市 $1$ 前往城市 $4$，具体操作如下：

• 在城市 $1$ 的兑换柜台中，使用 $2$ 个金币，在 $2$ 分钟内换取 $6$ 个银币。
• 使用第 $2$ 条铁路，在 $4$ 分钟内从城市 $1$ 前往城市 $3$。
• 使用第 $4$ 条铁路，在 $1$ 分钟内从城市 $3$ 前往城市 $4$。

示例输入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

这个输入中的铁路网络如下图所示：

你可以在 $16576$ 分钟内从城市 $1$ 前往城市 $6$，具体操作如下：

• 使用第 $1$ 条铁路，在 $1$ 分钟内从城市 $1$ 前往城市 $2$。
• 在城市 $2$ 的兑换柜台中，使用 $3$ 个金币，在 $9000$ 分钟内换取 $3$ 个银币。
• 使用第 $1$ 条铁路，在 $1$ 分钟内从城市 $2$ 前往城市 $1$。
• 使用第 $2$ 条铁路，在 $1$ 分钟内从城市 $1$ 前往城市 $3$。
• 在城市 $3$ 的兑换柜台中，使用 $8$ 个金币，在 $5600$ 分钟内换取 $8$ 个银币。
• 使用第 $2$ 条铁路，在 $1$ 分钟内从城市 $3$ 前往城市 $1$。
• 使用第 $1$ 条铁路，在 $1$ 分钟内从城市 $1$ 前往城市 $2$。
• 使用第 $3$ 条铁路，在 $1$ 分钟