题目描述

现在有 $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$
• 接下来 $m$ 行 $u_i,v_i,x_i,t_i$
• 接下来 $n$ 行 $c_i,d_i$

输出格式

按照这个顺序，对每个$t= 2,…, N$，打印一个包含从城市$1$ 到城市$t$所需最少时间的行。

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

2
14

The railway network in this input is shown in the figure below.

In this figure, each city is labeled as follows:

• The first line: the ID number $i$ of the city ($i$ for City $i$)
• The second line: $C_i$ / $D_i$

Similarly, each railroad is labeled as follows:

• The first line: the ID number $i$ of the railroad ($i$ for the $i$-th railroad in input)
• The second line: $A_i$ / $B_i$

You can travel from City $1$ to City $2$ in $2$ minutes, as follows:

• Use the $1$-st railroad to move from City $1$ to City $2$ in $2$ minutes.

You can travel from City $1$ to City $3$ in $14$ minutes, as follows:

• Use the $1$-st railroad to move from City $1$ to City $2$ in $2$ minutes.
• At the exchange counter in City $2$, exchange $3$ gold coins for $3$ silver coins in $6$ minutes.
• Use the $1$-st railroad to move from City $2$ to City $1$ in $2$ minutes.
• Use the $2$-nd railroad to move from City $1$ to City $3$ in $4$ minutes.

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

The railway network in this input is shown in the figure below:

You can travel from City $1$ to City $4$ in $7$ minutes, as follows:

• At the exchange counter in City $1$, exchange $2$ gold coins for $6$ silver coins in $2$ minutes.
• Use the $2$-nd railroad to move from City $1$ to City $3$ in $4$ minutes.
• Use the $4$-th railroad to move from City $3$ to City $4$ in $1$ minutes.

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

The railway network in this input is shown in the figure below:

You can travel from City $1$ to City $6$ in $16576$ minutes, as follows:

• Use the $1$-st railroad to move from City $1$ to City $2$ in $1$ minute.
• At the exchange counter in City $2$, exchange $3$ gold coins for $3$ silver coins in $9000$ minutes.
• Use the $1$-st railroad to move from City $2$ to City $1$ in $1$ minute.
• Use the $2$-nd railroad to move from City $1$ to City $3$ in $1$ minute.
• At the exchange counter in City $3$, exchange $8$ gold coins for $8$ silver coins in $5600$ minutes.
• Use the $2$-nd railroad to move from City $3$ to City $1$ in $1$ minute.
• Use the $1$-st railroad to move from City $1$ to City $2$ in $1$ minute.
• Use the $3$-rd railroad to move from City $2$ to City $4$ in $1$ minute.
• At the exchange counter in City $4$, exchange $19$ gold coins for $19$ silver coins in $1900$ minutes.
• Use the $3$-rd railroad to move from City $4$ to City $2$ in $1$ minute.
• Use the $1$-st railroad to move from City $2$ to City $1$ in $1$ minute.
• Use the $2$-nd railroad to move from City $1$ to City $3$ in $1$ minute.
• Use the $4$-th railroad to move from City $3$ to City $5$ in $1$ minute.
• At the exchange counter in City $5$, exchange $63$ gold coins for $63$ silver coins in $63$ minutes.
• Use the $4$-th railroad to move from City $5$ to City $3$ in $1$ minute.
• Use the $2$-nd railroad to move from City $3$ to City $1$ in $1$ minute.
• Use the $5$-th railroad to move from City $1$ to City $6$ in $1$ minute.

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

The railway network in this input is shown in the figure below:

2 1 0
1 2 1 1
1 1000000000
1 1

1000000001

The railway network in this input is shown in the figure below:

You can travel from City $1$ to City $2$ in $1000000001$ minutes, as follows:

• At the exchange counter in City $1$, exchange $1$ gold coin for $1$ silver coin in $1000000000$ minutes.
• Use the $1$-st railroad to move from City $1$ to City $2$ in $1$ minute.

提示

• $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$ 通过一些铁路到达。
• 输入中的所有值都是整数