AT_abc164_e [ABC164E] Two Currencies

[problemUrl]: https://atcoder.jp/contests/abc164/tasks/abc164_e $ 1 $ から $ N $ までの番号がつけられた $ N $ 個の都市があります。 これらの都市は $ M $ 本の鉄道路線によって結ばれています。 あなたは現在、金貨を $ 10^{100} $ 枚、銀貨を $ S $ 枚持った状態で都市 $ 1 $ にいます。 $ 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 $ への移動にかかる最小の時間を順番に一行ずつ出力せよ。

### 制約 - $ 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\