给定一个包含 $n$ 个顶点的连通无向图。每条边都有一个正整数权重，并被涂成红色或蓝色中的一种颜色。对于每个 $k \in \{0, \dots, n - 1\}$，请找出包含恰好 $k$ 条红色边的生成树的最小权重，或者判断不存在这样的生成树。

输入格式

第一行包含测试用例的数量 $Z$ ($1 \le Z \le 10\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含整数 $n, m$ ($2 \le n \le 100\,000, n - 1 \le m \le 200\,000$)，分别表示顶点数和边数。

接下来 $m$ 行描述图的边。每行包含三个整数 $u_i, v_i, w_i$ 以及一个字符 $c_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^6, c_i \in \{R, B\}$)，分别表示边的两个端点、权重和颜色。红色用 $R$ 表示，蓝色用 $B$ 表示。

保证图是连通的。所有测试用例的 $n$ 之和不超过 $500\,000$。所有测试用例的 $m$ 之和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，在一行中输出 $n$ 个整数 $a_0, \dots, a_{n-1}$。其中 $a_k$ 表示包含恰好 $k$ 条红色边的生成树的最小权重，如果不存在这样的生成树，则输出 $-1$。

样例

样例输入 1

2
4 6
1 2 1 R
2 3 5 B
3 4 1 R
4 1 5 B
1 3 1 R
2 4 3 B
3 3
1 2 5 R
1 3 7 R
2 3 9 B

样例输出 1

13 9 5 3
-1 14 12