题目描述

There are $N$ cities numbered $1$ to $N$, connected by $M$ railroads.

You are now at City $1$, with $10^{100}$ gold coins and $S$ silver coins in your pocket.

The $i$-th railroad connects City $U_i$ and City $V_i$ bidirectionally, and a one-way trip costs $A_i$ silver coins and takes $B_i$ minutes. You cannot use gold coins to pay the fare.

There is an exchange counter in each city. At the exchange counter in City $i$, you can get $C_i$ silver coins for $1$ gold coin. The transaction takes $D_i$ minutes for each gold coin you give. You can exchange any number of gold coins at each exchange counter.

For each $t=2, ..., N$, find the minimum time needed to travel from City $1$ to City $t$. You can ignore the time spent waiting for trains.

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

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

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

每个城市都有一个兑换处。在城市 $i$ 的兑换处，您可以用 $1$ 枚金币换取 $C_i$ 枚银币。每枚金币的交易时间为 $D_i$ 分钟。您可以在每个兑换柜台兑换任意数量的金币。

对于每个 $t=2, ..., N$ ，求从城市 $1$ 到城市 $t$ 所需的最短时间。你可以忽略等待火车的时间。

输入格式

输入内容按以下格式标准输入：

$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$

输出格式

For each $t=2, ..., N$ in this order, print a line containing the minimum time needed to travel from City $1$ to City $t$.

样例 #1

样例输入 #1

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

样例输出 #1

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

样例 #2

样例输入 #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

样例 #3

样例输入 #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

样例 #4

样例输入 #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

样例输入 #5

2 1 0
1 2 1 1
1 1000000000
1 1

样例输出 #5

1000000001

说明

数据规模与约定

• $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 \lt V_i \leq N$
• 不存在一对 $i, j(i \neq j)$ ，即 $(U_i,V_i)=(U_j,V_j)$ 。
• 每个城市 $t=2,...,N$ 都可以通过一定数量的铁路从城市 $1$ 到达。
• 所有输入值均为整数。

样例 $1$ 解释

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

在该图中，每个城市的标记如下：

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

同样，每条铁路的标签如下：

• 第一行：铁路的 ID 编号 $i$ （输入中第 $i$ 条铁路的 ID 编号为 $i$ )
• 第二行 $A_i$ / $B_i$

您可以在 $2$ 分钟内从城市 $1$ 到达城市 $2$ ，具体如下：

• 使用第 $1$ 条铁路在 $2$ 分钟内从城市 $1$ 到达城市 $2$ 。

您可以在 $14$ 分钟内从城市 $1$ 到达城市 $3$ ，具体如下：

• 使用第 $1$ 条铁路，从城市 $1$ 到城市 $2$ 只需 $2$ 分钟。
• 在城市 $2$ 的兑换处，用 $6$ 分钟将 $3$ 金币兑换成 $3$ 银币。
• 使用第 $1$ 条铁路在 $2$ 分钟内从城市 $2$ 移动到城市 $1$ 。
• 使用第 $2$ 条铁路，在 $4$ 分钟内从城市 $1$ 到达城市 $3$ 。

样例 $2$ 解释

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

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

• 在城市 $1$ 的兑换处用 $2$ 金币兑换 $6$ 银币，用时 $2$ 分钟。
• 使用第 $2$ 条铁路，在 $4$ 分钟内从城市 $1$ 移动到城市 $3$ 。
• 使用第 $4$ 条铁路，从城市 $3$ 到城市 $4$ 只需 $1$ 分钟。

样例 $3$ 解释

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

从城市 $1$ 到城市 $6$ 只需 $16576$ 分钟，具体如下：

• 使用第 $1$ 条铁路从城市 $1$ 到城市 $2$ 只需 $1$ 分钟。
• 在 $2$ 城的兑换处，用 $3$ 金币兑换 $3$ 银币，用时 $9000$ 分钟。
• 使用第 $1$ 条铁路，在 $1$ 分钟内从城市 $2$ 移动到城市 $1$ 。
• 使用第 $2$ 条铁路，在 $1$ 分钟内从城市 $1$ 到城市 $3$ 。
• 在城市 $3$ 的兑换柜台，用 $5600$ 分钟将 $8$ 金币兑换成 $8$ 银币。
• 使用第 $2$ 条铁路在 $1$ 分钟内从城市 $3$ 移动到城市 $1$ 。
• 使用第 $1$ 条铁路，在 $1$ 分钟内从城市 $1$ 到城市 $2$ 。
• 使用第 $3$ 条铁路，在 $1$ 分钟内从城市 $2$ 到城市 $4$ 。
• 在 $4$ 城的兑换处，用 $19$ 金币兑换 $19$ 银币，用时 $1900$ 分钟。
• 使用第 $3$ 条铁路，在 $1$ 分钟内从城市 $4$ 移动到城市 $2$ 。
• 使用第 $1$ 条铁路，在 $1$ 分钟内从城市 $2$ 到城市 $1$ 。
• 使用第 $2$ 条铁路，在 $1$ 分钟内从城市 $1$ 到城市 $3$ 。
• 使用第 $4$ 条铁路，在 $1$ 分钟内从城市 $3$ 到城市 $5$ 。
• 在 $5$ 城的兑换处，用 $63$ 金币兑换 $63$ 银币，用时 $63$ 分钟。
• 使用第 $4$ 条铁路，在 $1$ 分钟内从城市 $5$ 移动到城市 $3$ 。
• 使用第 $2$ 条铁路，在 $1$ 分钟内从城市 $3$ 到城市 $1$ 。
• 使用第 $5$ 条铁路，在 $1$ 分钟内从城市 $1$ 到城市 $6$ 。

样例 $4$ 解释

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

样例 $5$ 解释

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

您可以在 $1000000001$ 分钟内从城市 $1$ 到达城市 $2$ ，具体如下：

• 在城市 $1$ 的兑换处，用 $1$ 金币兑换 $1$ 银币，用时 $1000000000$ 分钟。
• 使用第 $1$ 条铁路，在 $1$ 分钟内从城市 $1$ 移动到城市 $2$ 。