import java.util.*;
import java.io.*;

public class rainbowgraph_font
{
   public static void main(String[] args) throws Exception
   {
      PrintWriter out = new PrintWriter(System.out);
      new rainbowgraph_font(new FastScanner(System.in), out);
      out.close();
   }

   int N, M, oo = 987654321;
   Edge[] edges;

   // Add the connection if removing some edge and replacing it maintains
   // connectivity.
   Graph buildExchange(boolean[] includedEdges, int color)
   {
      Graph g = new Graph(M);
      for (int i=0; i<M; i++)
      {
         if (includedEdges[i])
         {
            includedEdges[i] = false;

            DisjointSet ds = getComponents(includedEdges, color);
            if (ds.numComps == 1)
            {
               for (int j=0; j<M; j++)
               {
                  if (i != j && !includedEdges[j])
                  {
                     g.add(j, i);
                  }
               }
            }
            else
            {
               for (int j=0; j<M; j++)
               {
                  Edge e = edges[j];
                  if (i != j && !includedEdges[j] && (color&e.color) > 0 &&
                      ds.find(e.i) != ds.find(e.j))
                  {
                     g.add(j, i);
                  }
               }
            }

            includedEdges[i] = true;
         }
      }

      return g; 
   }

   // Modify includeEdges to be the new edges in the current solution set
   // Run one step of the matroid intersection algorithm.
   boolean augment(boolean[] includedEdges)
   {
      // Build a connection graph 
      Graph g = buildExchange(includedEdges, 1);
      Graph g2 = buildExchange(includedEdges, 2);
      g.mergeInto(g2.reversed());

      // If removing this edge still causes color 1 to be connected, then
      // this node is a source
      // Edge must currently be in the graph
      boolean[] isSource = new boolean[M];
      for (int i=0; i<M; i++)
      {
         if (includedEdges[i])
         {
            includedEdges[i] = false;
            isSource[i] = testConnectivity(includedEdges, 1);      
            includedEdges[i] = true;
         }
      }

      // If removing this edge still cases color 2 to be connected, then
      // this node is a sink
      // Edge must currently be in the graph
      boolean[] isSink = new boolean[M];
      for (int i=0; i<M; i++)
      {
         if (includedEdges[i])
         {
            includedEdges[i] = false;
            isSink[i] = testConnectivity(includedEdges, 2);      
            includedEdges[i] = true;
         }
      }

      // Find some path of exchanges from a source to a sink
      // Weights are on the nodes, some are negative weights so
      // use Bellman-Ford.
      
      int[] cost = new int[g.N];
      Arrays.fill(cost, oo);
      for (int i=0; i<g.N; i++)
         if (isSource[i])
            cost[i] = -edges[i].w;
      int[] prev = new int[g.N];
      Arrays.fill(prev, -1);
      boolean changed = true;
      while (changed)
      {
         changed = false;
         for (int i=0; i<g.N; i++) if (cost[i] < oo)
         {
            for (int j : g.adj[i])
            {
               int newCost = cost[i];
               newCost += includedEdges[j] ? -edges[j].w : edges[j].w;
               if (newCost < cost[j])
               {
                  cost[j] = newCost;
                  prev[j] = i;
                  changed = true;
               }
            }
         }
      }

      int minSinkCost = oo;
      int minSink = -1;
      for (int i=0; i<g.N; i++)
      {
         if (isSink[i] && cost[i] < minSinkCost)
         {
            minSinkCost = cost[i];
            minSink = i;
         }
      }

      if (minSink == -1)
         return false;
      
      int i = minSink;
      boolean dir = true;
      includedEdges[i] = false; 
      while (!isSource[i])
      {
         int j = prev[i];
         includedEdges[j] = dir;
         dir = !dir;
         i = j;
      }

      return true;
   }

   DisjointSet getComponents(boolean[] includedEdges, int color)
   {
      DisjointSet ds = new DisjointSet(N);
      for (int i=0; i<M; i++)
         if ((edges[i].color & color) > 0 && includedEdges[i]) 
            ds.union(edges[i].i, edges[i].j);
      return ds;
   }

   boolean testConnectivity(boolean[] includedEdges, int color)
   {
      return getComponents(includedEdges, color).numComps == 1;
   }

   boolean isConnected(boolean[] includedEdges)
   {
      return testConnectivity(includedEdges, 1) && testConnectivity(includedEdges, 2); 
   }

   int getCost(boolean[] includedEdges)
   {
      int res = 0;
      for (int i=0; i<M; i++)
         if (includedEdges[i])
            res += edges[i].w;
      return res; 
   }

   public rainbowgraph_font(FastScanner in, PrintWriter out)
   {
      
      N = in.nextInt();
      M = in.nextInt();
      edges = new Edge[M];
      for (int u=0; u<M; u++)
      {
         int i = in.nextInt()-1;
         int j = in.nextInt()-1;
         int w = in.nextInt();
         int color = -1;
         char c = in.next().charAt(0);

         // Colors are binary. It tells you which graph to keep the edge
         // in. (01=R, 10=B, 11=G)
         if (c == 'R')
            color = 1;
         else if (c == 'B')
            color = 2;
         else if (c == 'G')
            color = 3;
      
         edges[u] = new Edge(i, j, w, color);
      }
     
      boolean[] includedEdges = new boolean[M];
      Arrays.fill(includedEdges, true);
      
      int[] res = new int[M+1];
      Arrays.fill(res, -1);

      for (int numEdges=M; numEdges>=1; numEdges--)
      {
         res[numEdges] = getCost(includedEdges);
         if (!augment(includedEdges))
            break;
         if (!isConnected(includedEdges))
         {
            System.out.println("BADNESS");
            break;
         }
      }

      for (int u=1; u<=M; u++)
         out.println(res[u]);
   }
}

class Edge
{
   int i, j, w;
   int color;

   Edge(int ii, int jj, int ww, int cc)
   {
      i=ii; j=jj; w=ww; color=cc; 
   }
}

class DisjointSet
{
   int numComps;
   int[] p, r;
   DisjointSet(int s)
   {
      p = new int[s];
      r = new int[s];
      for(int i=0; i<s; i++)
         p[i] = i;
      numComps = s;
   }
   
   boolean union(int x, int y)
   {
      int a = find(x);
      int b = find(y);
      if(a==b) return false;
      numComps--;
      if(r[a] == r[b])
         r[p[b]=a]++;
      else 
         p[a]=p[b]=r[a]<r[b]?b:a;
      return true;
   }
   
   int find(int x) 
   {
      return p[x]=p[x]==x?x:find(p[x]);
   }
}

// This graph is the exchange graph for matroid intersection.
class Graph
{
   int N;
   ArrayList<Integer>[] adj;

   Graph(int NN)
   {
      adj = new ArrayList[N=NN];
      for (int i=0; i<N; i++)
         adj[i] = new ArrayList<>();
   }

   void add(int i, int j)
   {
      adj[i].add(j);
   }

   Graph reversed()
   {
      Graph rev = new Graph(N);
      for (int i=0; i<N; i++)
         for (int j : adj[i])
            rev.add(j, i);
      return rev; 
   }

   void mergeInto(Graph rhs)
   {
      for (int i=0; i<rhs.N; i++)
         for (int j : rhs.adj[i])
            add(i, j);
   }
}

class FastScanner
{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    
    public FastScanner(InputStream stream)
    {
        this.stream = stream;
    }
    
    int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars){
            curChar = 0;
            try{
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }
    
    boolean isSpaceChar(int c)
    {
        return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
    }
    
    boolean isEndline(int c)
    {
        return c=='\n'||c=='\r'||c==-1;
    }
    
    int nextInt()
    {
        return Integer.parseInt(next());
    }
    
    long nextLong()
    {
        return Long.parseLong(next());
    }
    
    double nextDouble()
    {
        return Double.parseDouble(next());
    }
    
    String next(){
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isSpaceChar(c));
        return res.toString();
    }
    
    String nextLine(){
        int c = read();
        while (isEndline(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isEndline(c));
        return res.toString();
    }
}