Problem Description

Kenkoooo is planning a trip in the Snuuk country. There are $ n $ cities in Snuuk, and $ m $ trains running between them. The cities are numbered from $ 1 $ to $ n $, and the $ i $-th train runs bidirectionally between city $ u_i $ and city $ v_i $. It is possible to reach any city from any other city by transferring trains.

There are two types of currency used in Snuuk: yen and snuuk. The fare for any train can be paid in either yen or snuuk. The fare for the $ i $-th train is $ a_i $ yen if paid in yen, and $ b_i $ snuuk if paid in snuuk.

If you visit a city with a currency exchange office, you can exchange all your yen into snuuk at a rate of $ 1 $ yen to $ 1 $ snuuk. However, you must exchange all your yen at once when you do this. Currently, all $ n $ cities have currency exchange offices, but the exchange office in the $ i $-th city will close $ i $ years from now and will no longer be available after that.

Kenkoooo has $ 10^{15} $ yen and plans to start his trip from city $ s $ and travel to city $ t $. During his journey, he wants to exchange his yen for snuuk at one of the exchange offices in the cities he visits. He can do this at the exchange office in city $ s $ or city $ t $ as well.

Kenkoooo wants to maximize the amount of snuuk he has when he reaches city $ t $ by choosing the optimal path and exchange city. For each $ i=0,...,n-1 $, find the maximum amount of snuuk Kenkoooo can have when he travels from city $ s $ to city $ t $ after $ i $ years. Note that no year will pass during the trip.

Input Format

The input is given from the standard input in the following format:

$ n $ $ m $ $ s $ $ t $ $ u_1 $ $ v_1 $ $ a_1 $ $ b_1 $ $ : $ $ u_m $ $ v_m $ $ a_m $ $ b_m $

Output Format

Output $ n $ lines. The $ i $-th line should contain the maximum amount of snuuk Kenkoooo can have when he travels from city $ s $ to city $ t $ after $ i-1 $ years.

Sample Input and Output

Sample Input #1

4 3 2 3
1 4 1 100
1 2 1 10
1 3 20 1

Sample Output #1

999999999999998
999999999999989
999999999999979
999999999999897

Sample Input #2

8 12 3 8
2 8 685087149 857180777
6 7 298270585 209942236
2 4 346080035 234079976
2 5 131857300 22507157
4 8 30723332 173476334
2 6 480845267 448565596
1 4 181424400 548830121
4 5 57429995 195056405
7 8 160277628 479932440
1 6 475692952 203530153
3 5 336869679 160714712
2 7 389775999 199123879

Sample Output #2

999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994
999999574976994

Notes/Hints

Constraints

• $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 < v_i \leq n$
• $1 \leq a_i, b_i \leq 10^9$
• $u_i \neq u_j$ or $v_i \neq v_j$ for $i \neq j$
• It is possible to reach any city from any other city by transferring trains.
• All inputs are integers.

Sample Explanation 1

The optimal exchange city for $ 0 $ years is city $ 1 $. For $ 1 $ year, the optimal exchange city is city $ 2 $. Note that even if the exchange office closes, it is still possible to visit city $ 1 $. Also, note that leaving some yen and exchanging the rest is not allowed. For $ 2 $ years, the optimal exchange city is city $ 3 $. For $ 3 $ years, the optimal exchange city is city $ 4 $. Note that using the same train multiple times is allowed.

见题面 Input 部分

见题面 Output 部分