F. Red-Blue MST
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a connected undirected graph on $$$n$$$ vertices. Each edge has a positive integer weight and is painted in one of two colors – red or blue. For each $$$k \in \{0, \ldots, n-1\}$$$, find the minimum possible weight of a spanning tree that contains exactly $$$k$$$ red edges or decide that no such spanning tree exists.

Input

The first line of input contains the number of test cases $$$Z$$$ ($$$1 \leq Z \leq 10\,000$$$). The descriptions of the test cases follow.

The first line of each test case contains integers $$$n$$$, $$$m$$$ ($$$2 \leq n \leq 100\,000$$$, $$$n-1 \leq m \leq 200\,000$$$) – the number of vertices and the number of edges.

Next $$$m$$$ lines describe graph edges. Each line contains three integers $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ followed by a character $$$c_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$1 \leq w_i \leq 10^6$$$, $$$c_i \in \{R,B\}$$$) – the two endpoints of an edge, its weight, and its color. The color red is denoted by $$$R$$$ and the color blue is denoted by $$$B$$$.

It is guaranteed that the graph is connected. The sum of $$$n$$$ over all test cases does not exceed $$$500\,000$$$. The sum of $$$m$$$ over all test cases does not exceed $$$1\,000\,000$$$.

Output

For each test case, print in a single line $$$n$$$ integers $$$a_0, \ldots, a_{n-1}$$$. $$$a_k$$$ should be the minimum possible weight of a spanning tree that contains exactly $$$k$$$ red edges, or $$$-1$$$ if no such spanning tree exists.

Example
Input
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
Output
13 9 5 3 
-1 14 12