题目描述

有 $n$ 个城市，它们由 $m$ 条双向道路连接，保证它们能够彼此到达。第 $i$ 条道路连接 $u_i,v_i$，需要花费 $a_i$ 个银币，耗费 $b_i$ 秒的时间。每个城市处都有兑换银币处，第 $i$ 个城市中你可以用 $1$ 个金币兑换 $c_i$ 个银币，可以兑换无限次，不过兑换 $1$ 次需要花费 $d_i$ 秒的时间。你一开始在 $1$ 号城市，有 $s$ 个银币和无限多的金币，求到其它城市需要耗费的最小时间。

输入格式

第一行 $n,m,s$

接下来 $m$ 行 $u_i,v_i,a_i,b_i$

接下来 $n$ 行 $c_i,d_i$

输出格式

输出 $n-1$ 行，第 $i$ 行表示城市 $1$ 到 $i$ 的最小时间。

样例 #1

样例输入 #1

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

样例输出 #1

2
14

一开始有一个银币 $s=1$ 。

对于城市 $2$ ，你可以直接用 $1$ 个银币的路费，花费 $2$ 秒的时间到达城市 $2$ ，总用时 $2$ 秒。

对于城市 $3$ ，你可以先用 $1$ 个银币的路费，花费 $2$ 秒的时间到达城市 $2$ ；然后在城市 $2$ 用 $3$ 个金币换 $3$ 个银币，花费 $6$ 秒；然后用 $1$ 个银币的路费，花费 $2$ 秒的时间回到城市 $1$ ，再从城市 $1$ 用 $2$ 个银币的路费，花费 $4$ 秒的时间到达城市 $3$ ，总用时 $14$ 秒。

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

提示

对于 $100\%$ 的数据：

• $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$
• 数据保证没有重边。
• 数据保证城市可达。
• 所有数据都是整数。