AT_soundhound2018_summer_qual_d Saving Snuuk

[problemUrl]: https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d kenkoooo さんはすぬけ国での旅行の計画を立てています。 すぬけ国には $ n $ 個の都市があり、$ m $ 本の電車が走っています。 都市には $ 1 $ から $ n $ の番号がつけられていて、 $ i $ 番目の電車は都市 $ u_i $ と $ v_i $ の間を両方向に走っています。 どの都市からどの都市へも電車を乗り継ぐことで到達できます。 すぬけ国で使える通貨には、円とスヌークの $ 2 $ 種類があります。 どの電車の運賃も円とスヌークのどちらの通貨でも支払え、 $ i $ 番目の電車の運賃は、 円で支払う場合 $ a_i $ 円、 スヌークで払う場合 $ b_i $ スヌークです。 両替所のある都市に行くと、$ 1 $ 円を $ 1 $ スヌークに両替することができます。 ただし、 両替をするときには持っている円すべてをスヌークに両替しなければなりません。 つまり、kenkoooo さんの所持金が $ X $ 円であるときに両替をすると、 kenkoooo さんの所持金は $ X $ スヌークになります。 現在、両替所は $ n $ 個の都市すべてに存在しますが、 $ i $ 番目の都市の両替所は今年から $ i $ 年後に閉鎖されてしまい、 $ i $ 年後とそれ以降は使うことができません。 kenkoooo さんは $ 10^{15} $ 円を持って都市 $ s $ から旅に出て、 都市 $ t $ へ向かおうと思っています。 移動中、kenkoooo さんは両替所のある都市のいずれかで円をスヌークに両替しようと考えています。 ただし、都市 $ s $ または都市 $ t $ の両替所で両替をしてもよいものとします。 kenkoooo さんは移動の経路と両替をする都市を適切に選ぶことで、できるだけ多くのスヌークを持っている状態で 都市 $ t $ に辿り着きたいと考えています。 $ i=0,...,n-1 $ のそれぞれについて、$ i $ 年後に都市 $ s $ から都市 $ t $ へ移動した際に kenkoooo さんが所持しているスヌークの最大額を求めてください。 ただし、旅行中に年をまたぐことは無いとします。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ m $ $ s $ $ t $ $ u_1 $ $ v_1 $ $ a_1 $ $ b_1 $ $ : $ $ u_m $ $ v_m $ $ a_m $ $ b_m $

$ n $ 行出力せよ。 $ i $ 行目には、 $ i-1 $ 年後に都市 $ s $ から都市 $ t $ へ移動した際に kenkoooo さんの所持しているスヌークの最大額を出力せよ。

### 制約 - $ 2\ \leq\ n\ \leq\ 10^5 $ - $ 1\ \leq\ m\ \leq\ 10^5 $ - $ 1\ \leq\ s,t\ \leq\ n $ - $ s\ \neq\ t $ - $ 1\ \leq\ u_i\