問題文

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

この地方には $K$ 種類の動物が生息しており，動物の種類は $1, 2, \dots, K$ の整数で表されます． 各道には，各種類の動物が高々 $1$ 匹居ます． 動物たちは人懐こく，動物の居る道を通るとそこに居た動物は一緒についてきます． ただし，各動物は人間よりも同種の動物の方を好むため，動物 $k$ を連れた状態で動物 $k$ の居る道を通ると，居合わせた動物 $k$ は連れ立ってどこかへ行ってしまいます．

街 $1, 2, \dots, N - 1$ には研究員が住んでおり，これから研究所に出勤しようとしていますが，Y.Y. 博士を喜ばせるために $1$ 匹以上の動物を連れていこうと考えています． しかし，あまり遠回りしていると遅刻してしまうかもしれません． それぞれの研究員のために，街 $i$ $(1 \le i \le N - 1)$ から街 $N$ への移動経路であって，研究所に着いた時点で少なくとも $1$ 匹の動物を連れているようなもののうち，道の長さの総和が最小となるものを求めてあげてください． ただし，今回の研究員はそこまでお人好しではないので，各移動経路では同じ街や同じ道を複数回経由することは許さないものとします． また，街の中に動物は居らず，各研究員は出発時点で動物を一切連れていないものとし，移動経路は研究員ごとに独立に（他の研究員の移動による影響は無視して）考えてください．

入力

$N$ $M$ $K$
$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 K \le 30$
• $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$ は 0 と 1 からなる長さ $K$ の文字列である．
• 街には $1, 2, \dots, N$ の番号が付いている．
• 道には $1, 2, \dots, M$ の番号が付いている．
• 道 $j$ は街 $A_j$ と街 $B_j$ を双方向に結び，その長さは $C_j$ である．
• $X_j$ の左から $k$ 文字目は道 $j$ に居る動物 $k$ の数を表す．
• 任意の街から任意の街に，道を何本か経由することで到達可能である．
• 入力は $X_j \ (1 \le j \le M)$ を除き全て整数である．

出力

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

$i$ 行目には，研究所に着いた時点で少なくとも $1$ 匹の動物を連れているような街 $i$ から街 $N$ への移動経路における道の長さの総和の最小値を出力してください． ただし，条件を満たす移動経路が存在しない $i$ に対しては $-1$ を出力してください．

サンプル

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

1
-1

4 6 2
1 2 4 11
1 3 2 10
1 4 1 10
2 3 2 00
3 4 1 00
3 4 4 01

1
5
4

8 15 3
3 2 2 000
5 7 4 011
8 3 8 000
3 7 4 000
2 4 7 010
7 1 1 110
3 1 10 000
5 1 10 100
2 5 8 010
6 1 1 011
2 1 6 010
6 1 10 010
6 4 8 101
2 1 6 101
4 2 6 001

13
19
-1
16
16
14
17