两种货币

题目描述

有 $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$ 所需的最短时间。等电车花费的时间可以忽略不计。

输入格式

输入按以下格式从标准输入给出:

$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$ 所需的最短时间。

样例

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

2
14

可以按如下方式行动,用 $2$ 分钟从城市 $1$ 移动到城市 $2$:

• 使用第 $1$ 条铁路线路,从城市 $1$ 移动到城市 $2$。(所需时间: $2$ 分钟)

可以按如下方式行动,用 $14$ 分钟从城市 $1$ 移动到城市 $3$:

• 使用第 $1$ 条铁路线路,从城市 $1$ 移动到城市 $2$。(所需时间: $2$ 分钟)
• 在城市 $2$ 的兑换处,将 $3$ 枚金硬币兑换成 $3$ 枚银硬币。(所需时间: $6$ 分钟)
• 使用第 $1$ 条铁路线路,从城市 $2$ 移动到城市 $1$。(所需时间: $2$ 分钟)
• 使用第 $2$ 条铁路线路,从城市 $1$ 移动到城市 $3$。(所需时间: $4$ 分钟)

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

5
5
7

可以按如下方式行动,用 $7$ 分钟从城市 $1$ 移动到城市 $4$:

• 在城市 $1$ 的兑换处,将 $2$ 枚金硬币兑换成 $6$ 枚银硬币。(所需时间: $2$ 分钟)
• 使用第 $2$ 条铁路线路,从城市 $1$ 移动到城市 $3$。(所需时间: $4$ 分钟)
• 使用第 $4$ 条铁路线路,从城市 $3$ 移动到城市 $4$。(所需时间: $1$ 分钟)

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

1
9003
14606
16510
16576

可以按如下方式行动,用 $16576$ 分钟从城市 $1$ 移动到城市 $6$:

• 使用第 $1$ 条铁路线路,从城市 $1$ 移动到城市 $2$。(所需时间: $1$ 分钟)
• 在城市 $2$ 的兑换处,将 $3$ 枚金硬币兑换成 $3$ 枚银硬币。(所需时间: $9000$ 分钟)
• 使用第 $1$ 条铁路线路,从城市 $2$ 移动到城市 $1$。(所需时间: $1$ 分钟)
• 使用第 $2$ 条铁路线路,从城市 $1$ 移动到城市 $3$。(所需时间: $1$ 分钟)
• 在城市 $3$ 的兑换处,将 $8$ 枚金硬币兑换成 $8$ 枚银硬币。(所需时间: $5600$ 分钟)
• 使用第 $2$ 条铁路线路,从城市 $3$ 移动到城市 $1$。(所需时间: $1$ 分钟)
• 使用第 $1$ 条铁路线路,从城市 $1$ 移动到城市 $2$。(所需时间: $1$ 分钟)
• 使用第 $3$ 条铁路线路,从城市 $2$ 移动到城市 $4$。(所需时间: $1$ 分钟)
• 在城市 $4$ 的兑换处,将 $19$ 枚金硬币兑换成 $19$ 枚银硬币。(所需时间: $1900$ 分钟)
• 使用第 $3$ 条铁路线路,从城市 $4$ 移动到城市 $2$。(所需时间: $1$ 分钟)
• 使用第 $1$ 条铁路线路,从城市 $2$ 移动到城市 $1$。(所需时间: $1$ 分钟)
• 使用第 $2$ 条铁路线路,从城市 $1$ 移动到城市 $3$。(所需时间: $1$ 分钟)
• 使用第 $4$ 条铁路线路,从城市 $3$ 移动到城市 $5$。(所需时间: $1$ 分钟)
• 在城市 $5$ 的兑换处,将 $63$ 枚金硬币兑换成 $63$ 枚银硬币。(所需时间: $63$ 分钟)
• 使用第 $4$ 条铁路线路,从城市 $5$ 移动到城市 $3$。(所需时间: $1$ 分钟)
• 使用第 $2$ 条铁路线路,从城市 $3$ 移动到城市 $1$。(所需时间: $1$ 分钟)
• 使用第 $5$ 条铁路线路,从城市 $1$ 移动到城市 $6$。(所需时间: $1$ 分钟)

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

1
3
5

2 1 0
1 2 1 1
1 1000000000
1 1

1000000001

可以按如下方式行动,用 $1000000001$ 分钟从城市 $1$ 移动到城市 $2$:

• 在城市 $1$ 的兑换处,将 $1$ 枚金硬币兑换成 $1$ 枚银硬币。(所需时间: $1000000000$ 分钟)
• 使用第 $1$ 条铁路线路,从城市 $1$ 移动到城市 $2$。(所需时间: $1$ 分钟)

数据范围

• $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$
• 不存在 $(U_i,V_i)=(U_j,V_j)$ 的 $i,j(i \neq j)$
• 可以使用若干条铁路线路从城市 $1$ 移动到城市 $t=2,...,N$。
• 输入均为整数。