/*
Criteria:
1.read the problem carefully; WRITE DOWN SPECIAL CONSTRAINTS when the problem is long;
2.consider special situations/constraints to get observations;
3.think of everything throughout before coding;
4.return to the initial list of notifications after coding.

CONSTRAINTS:

OBSERVATIONS:

OTHER NOTIFICATIONS:

THINK CAREFULLY AND CODE DETERMINEDLY!
*/
#include<bits/stdc++.h>
using namespace std;
int n,m;
int X[110],Y[110],Z[110];
char s[110];
bool on[110];
struct DSU{
int dsu[110];
bool fit[110];
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
bool merge(int x,int y){x=find(x),y=find(y);if(x==y)return false;dsu[x]=y;return true;}
int num;
void init(){
	for(int i=1;i<=n;i++)dsu[i]=i;
	num=0;
	for(int i=1;i<=m;i++)if(fit[i]&&!on[i])num+=merge(X[i],Y[i]);
}
bool valid(int i){
	return num==n-1||num==n-2&&fit[i]&&find(X[i])!=find(Y[i]);
}
}RG,BG;
int res[110];
int sum;
int fr[110],val[110],dep[110],dis[110];
bool in[110];
vector<int>v[110];
bool Matriod_Intersection(){
	memset(dis,0x3f,sizeof(dis)),memset(dep,0x3f,sizeof(dep));
	for(int i=0;i<=m+1;i++)v[i].clear();
	for(int i=1;i<=m;i++)if(!on[i]){
		on[i]=true;
		RG.init(),BG.init();
		on[i]=false;
		if(RG.num==n-1)v[0].push_back(i);
		if(BG.num==n-1)v[i].push_back(m+1);
		for(int j=1;j<=m;j++)if(on[j]){
			if(RG.valid(j))v[j].push_back(i);
			if(BG.valid(j))v[i].push_back(j);
		}
	}
	for(int i=1;i<=m;i++)if(!on[i])val[i]=-Z[i];else val[i]=Z[i];
	queue<int>q;
	dis[0]=dep[0]=0,in[0]=true,q.push(0);
	while(!q.empty()){
		int x=q.front();q.pop(),in[x]=false;
		for(auto y:v[x])
			if(make_pair(dis[y],dep[y])>make_pair(dis[x]+val[y],dep[x]+1)){
				dis[y]=dis[x]+val[y];
				dep[y]=dep[x]+1;
				fr[y]=x;
				if(!in[y])q.push(y),in[y]=true;
			}
	}
	if(dis[m+1]>(1<<25))return false;
	sum+=dis[m+1];
	for(int i=fr[m+1];i;i=fr[i])on[i]^=1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)scanf("%d%d%d%s",&X[i],&Y[i],&Z[i],s+i);
	for(int i=1;i<=m;i++){
		if(s[i]!='R')BG.fit[i]=true;
		if(s[i]!='B')RG.fit[i]=true;
	}
	memset(res,-1,sizeof(res));
	RG.init(),BG.init();
	// printf("<%d,%d>\n",RG.num,BG.num);
	if(RG.num==n-1&&BG.num==n-1){
		sum=accumulate(Z+1,Z+m+1,0);
		res[m]=sum;
		for(int i=m-1;i;i--)
			if(Matriod_Intersection())res[i]=sum;
			else break;
	}
	for(int i=1;i<=m;i++)printf("%d\n",res[i]);
	return 0;
}
/*
5 8
1 5 1 R
2 1 2 R
5 4 5 R
4 5 3 G
1 3 3 G
4 3 5 G
5 4 1 B
1 2 2 B
*/