图

给定一个 $n$ 个顶点 $m$ 条边的无向图，每条边有一个边权，且属于 A/B/C 三个类别中的一个。你需要从中选择 $k$ 条边，和 $n$ 个顶点组成一个新图，满足新图去掉所有A类边后图仍然连通，新图去掉所有B类边后图也仍然连通。问这 $k$ 条边的最小边权之和是多少？如果不存在这样的方案，请输出 -1。

你需要对 $k=1,2,3,...,m$ 按顺序给出 $m$ 个答案。

第一行 2 个整数 $n, m$，分别表示顶点数和边数。

接下来 m 行每行三个整数 $u_i, v_i, w_i$ 和一个字符 $c_i$，表示 $u_i$ 到 $v_i$ 有一条边权为 $w_i$ 无向边，且类别为 $c_i$。

数据保证 $1\le n,m\le 100$，$1\le u_i,v_i\le n$，$1\le w_i\le 1000$，$c_i\in \{A,B,C\}$。

输出 $m$ 行，第 $i$ 行包含一个整数，表示 $k=i$ 时的最小边权之和，或者 -1 表示方案不存在。

5 8
1 5 1 A
2 1 2 A
5 4 5 A
4 5 3 C
1 3 3 C
4 3 5 C
5 4 1 B
1 2 2 B

-1
-1
-1
-1
15
14
17
22

杭州电子科技大学第二十二届程序设计竞赛