#P18335. Red-Blue MST

Red-Blue MST

Red-Blue MST

给定一张有 nn 个顶点的连通无向图。每条边都有正整数权值,并被涂成红色或蓝色。

对于每个 k∈{0,…,n−1}k\in\{0,\ldots,n-1\},求恰好包含 kk 条红边的生成树的最小总权值;如果这样的生成树不存在,则报告不存在。

输入格式

第一行包含测试用例数 ZZ。

每组测试用例的第一行包含两个整数 n,mn,m,表示顶点数和边数。

接下来 mm 行,每行包含三个整数 ui,vi,wiu_i,v_i,w_i,后跟一个字符 cic_i,表示一条端点为 ui,viu_i,v_i、权值为 wiw_i 的无向边。字符 R 表示红色,B 表示蓝色。

保证整张图连通,没有自环。允许重边,同一对端点之间可以有多条边,包括颜色相同或不同的边。

输出格式

对于每组测试用例,输出一行 nn 个整数 a0,…,an−1a_0,\ldots,a_{n-1}。

aka_k 是恰好包含 kk 条红边的生成树的最小总权值。如果不存在,则 ak=−1a_k=-1。

数据范围

  • 1≤Z≤100001\le Z\le10000;
  • 2≤n≤1000002\le n\le100000;
  • n−1≤m≤200000n-1\le m\le200000;
  • 1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i;
  • 1≤wi≤10000001\le w_i\le1000000;
  • ci∈{R,B}c_i\in\{\texttt{R},\texttt{B}\};
  • 所有测试用例的 nn 之和不超过 500000500000;
  • 所有测试用例的 mm 之和不超过 10000001000000。

样例输入 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