E - 两种货币

现在有 $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$ 的最少时间。可以忽略等待车的时间。

限制：

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

输出：

2
14

样例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

输出：

5
5
7

样例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

输出：

1
9003
14606
16510
16576

样例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

输出：

1
3
5

样例5：

输入：

2 1 0
1 2 1 1
1 1000000000
1 1

输出：

1000000001