AT_abc164_e [ABC164E] Two Currencies

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

- 第一行 $n,m,s$ - 接下来 $m$ 行 $u_i,v_i,x_i,t_i$ - 接下来 $n$ 行 $c_i,d_i$

输出 $n - 1$ 行，第 $i$ 行一个整数表示到第 $i + 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\