問題文

$i=1,\dots,M$ に対し以下の条件をすべて満たす長さ $N$ の非負整数列 $A=(A_1,A_2,\dots,A_N)$ が存在するか判定し、存在する場合は総和が最小のものを求めてください。

• $A_{x_i}+A_{y_i}\ge v_i \Rightarrow l_i \le A_{z_i} \le r_i$

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• $1\le T\le 2\times 10^{5}$
• $1\le N,M\le 2\times 10^5$
• $1\le x_i,y_i,z_i\le N$
• $0\le v_i,l_i,r_i\le 10^9$
• ひとつの入力に対する $N$ の総和は $2\times 10^5$ 以下
• ひとつの入力に対する $M$ の総和は $2\times 10^5$ 以下

入力

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で与えられます。

$N$ $M$
$x_1$ $y_1$ $z_1$ $v_1$ $l_1$ $r_1$
$x_2$ $y_2$ $z_2$ $v_2$ $l_2$ $r_2$
$\vdots$
$x_M$ $y_M$ $z_M$ $v_M$ $l_M$ $r_M$

出力

各テストケースについて、条件を満たす整数列が存在しない場合は -1 を、存在する場合は総和が最小の整数列 $A$ の各要素を空白区切りで出力してください。

サンプル

3
3 3
1 2 3 0 1 5
1 3 2 4 2 7
2 3 1 1 3 4
1 2
1 1 1 0 1 1
1 1 1 0 2 2
4 1
1 2 3 3 2 1

3 2 1
-1
0 0 0 0