問題文

Y.Y. 博士は動物が大好きです． Y.Y. 博士の居る研究所周辺には $1, 2, \dots, N$ の番号が付いた $N$ 個の街があり，研究所は街 $N$ の中にあります． 街同士は双方向に通行可能な $M$ 本の道で結ばれており，$j$ 番目の道は長さ $C_j$ で街 $A_j$ と街 $B_j$ を結んでいます． また，任意の街から任意の街に，道を何本か経由することで移動できます．

この地方には人懐こい動物が生息しており，動物の居る道を通るとそこに居た動物は一緒についてきます． また，少なくとも $1$ 本の道に動物が居ます．

街 $1, 2, \dots, N - 1$ には研究員が住んでおり，これから研究所に出勤しようとしていますが，Y.Y. 博士を喜ばせるために $1$ 匹以上の動物を連れていこうと考えています． しかし，あまり遠回りしていると遅刻してしまうかもしれません． それぞれの研究員のために，街 $i$ $(1 \le i \le N - 1)$ から街 $N$ への移動経路であって，動物の居る道を少なくとも $1$ 回通るようなもののうち，道の長さの総和が最小となるものを求めてあげてください． ただし，各移動経路では同じ街や同じ道を複数回経由してもよいものとし，途中で研究所に出勤しないで街 $N$ を素通りすることも可能であるとします．

入力

$N$ $M$
$A_1\ \ B_1\ \ C_1\ \ X_1$
$A_2\ \ B_2\ \ C_2\ \ X_2$
      $\vdots$
$A_M\ \ B_M\ \ C_M\ \ X_M$

• $2 \le N \le 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le A_j, B_j \le N,\ A_j \neq B_j \ \ (1 \le j \le M)$
• $1 \le C_j \le 10^9 \ \ (1 \le j \le M)$
• $X_j \in \{0, 1\} \ \ (1 \le j \le M)$
• 街には $1, 2, \dots, N$ の番号が付いている．
• 道には $1, 2, \dots, M$ の番号が付いている．
• 道 $j$ は街 $A_j$ と街 $B_j$ を双方向に結び，その長さは $C_j$ である．
• $X_j$ は道 $j$ に居る動物の数を表し，$X_j = 1$ であるような $j$ が少なくとも $1$ つ存在する．
• 任意の街から任意の街に，道を何本か経由することで到達可能である．
• 入力は全て整数である．

出力

$N - 1$ 行に渡って出力してください．

$i$ 行目には，動物の居る道を少なくとも $1$ 回通るような街 $i$ から街 $N$ への移動経路における道の長さの総和の最小値を出力してください． 本問題の設定と入力制約の下では，そのような移動経路が必ず存在することが保証されます．

サンプル

3 3
1 2 3 1
1 3 1 1
2 3 1 0

1
3

4 6
1 2 4 1
1 3 2 0
1 4 1 1
2 3 2 0
3 4 1 0
3 4 4 1

1
5
3

7 15
2 1 5 1
3 7 10 1
1 5 6 1
5 1 10 1
7 4 8 0
2 4 4 0
7 1 7 0
3 7 3 0
2 3 7 1
1 7 8 0
1 3 6 1
7 2 6 0
5 3 9 0
1 6 3 0
2 5 5 0

9
10
10
14
13
12