#include <fstream>
#include <vector>
#include <algorithm>
#define inf 2000000
using namespace std;

ifstream cin("ninjago.in");
ofstream cout("ninjago.out");
vector <int> v[31205];
int viz[31205],n,m,c[31205],cost[31205]={0};
int cerinta;
struct euri
{
    int vf1,vf2,val,cst;
}e[31205];
bool cmp(euri i, euri j)
{
    if(i.val==j.val)
        return i.cst<j.cst;
    return (i.val<j.val);
}
bool cmp2(int i, int j)
{
    return cost[i]<cost[j];
}
int findd(int i)
{
    int y,r=i;
    while(viz[r]!=r)
        r=viz[r];
    while(i!=viz[i])
    {
        y=viz[i];
        viz[i]=r;
        i=y;
    }
    return r;
}
void bfs(int i,int cont)
{
    int st=1,dr=1,l,j;
    viz[i]=cont;
    c[st]=i;
    while(st<=dr)
    {
        l=v[c[st]].size();
        for(j=0;j<l;j++)
            if(viz[v[c[st]][j]]==0)
        {
            viz[v[c[st]][j]]=cont;
            dr++;
            c[dr]=v[c[st]][j];
        }
        st++;
    }
}

void rez_1()
{
    int i,j,x,y,cnt=1;
    char car;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int ok=1;
        cin>>x>>y;
        for(j=1;j<=4;j++)
        {
            cin>>car;
            if(car=='E')
            {
               ok=0;
            }
        }
        if(ok)
        {
            v[x].push_back(y);
            v[y].push_back(x);
        }
    }
    bfs(1,1);
    for(j=2;j<=n;j++)
    {
        if(viz[j]!=0)
            cnt++;
    }
    cout<<cnt;
}
void reunire(int i, int j)
{
    viz[findd(i)]=findd(j);
}
void rez_2()
{
    int i,j,x,y,cnt=1,ok[31205],nr=0,vale,s=0;
    char car;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        vale=0;
        cin>>x>>y;
        for(j=1;j<=4;j++)
        {
            cin>>car;
            if(car=='E')
            {
               vale++;
            }
        }
        if(vale==0)
        {
            v[x].push_back(y);
            v[y].push_back(x);
        }
        else
        {
            nr++;
            e[nr].vf1=x;
            e[nr].vf2=y;
            e[nr].val=vale;
        }
    }
    viz[1]=1;
    bfs(1,1);
    for(j=1;j<=n;j++)
    {
        if(viz[j]==0)
        {
            viz[j]=j;
            cnt++;
            bfs(j,j);
        }
        ok[j]=inf;
    }
    cout<<cnt-1<<endl;
    sort(e+1,e+nr+1,cmp);
    //for(i=1;i<=nr;i++)
    //    cout<<e[i].vf1<<" "<<e[i].vf2<<" "<<e[i].val<<endl;
    for(i=1;i<=nr;i++)
    {
        if(findd(e[i].vf1)!=findd(e[i].vf2))
        {
            reunire(e[i].vf1,e[i].vf2);
            s+=e[i].val;
        }
    }
    cout<<s;
}
void rez_3()
{
    int i,j,val1,val2,val3,cnt=1,nr=0,vale,s=0,x[31205],y[31205],lng=0,ins[31205];
    unsigned long long ans=0;
    char car;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        vale=0;
        cin>>val1>>val2;
        val3=0;
        for(j=1;j<=4;j++)
        {
            int prod;
            if(j==1)
                prod=1;
            if(j==2)
                prod=5;
            if(j==3)
                prod=25;
            if(j==4)
                prod=125;
            cin>>car;
            if(car=='E')
            {
               vale++;
            }
            if(car=='D')
                val3+=4*prod;
            if(car=='C')
                val3+=3*prod;
            if(car=='B')
                val3+=2*prod;
            if(car=='A')
                val3+=prod;
        }
        if(vale==0)
        {
            lng++;
            x[lng]=val1;
            y[lng]=val2;
            cost[lng]=val3;
            ins[lng]=lng;
        }
        else
        {
            nr++;
            e[nr].vf1=val1;
            e[nr].vf2=val2;
            e[nr].val=vale;
            e[nr].cst=val3;
        }
    }
    for(i=1;i<=n;i++)
        viz[i]=i;
    sort(ins+1,ins+1+lng,cmp2);
    for(i=1;i<=lng;i++)
    {
        if(findd(x[ins[i]])!=findd(y[ins[i]]))
        {
            cout<<x[ins[i]]<<" "<<y[ins[i]]<<" "<<cost[ins[i]]<<endl;
            reunire(x[ins[i]],y[ins[i]]);
            ans+=cost[ins[i]];
        }
    }
    sort(e+1,e+nr+1,cmp);
    for(i=1;i<=nr;i++)
    {
        if(findd(e[i].vf1)!=findd(e[i].vf2))
        {
            cout<<e[i].vf1<<" "<<e[i].vf2<<" "<<e[i].cst<<endl;
            reunire(e[i].vf1,e[i].vf2);
            ans+=e[i].cst;
        }
    }
    cout<<ans;
}
int main()
{
    cin>>cerinta;
    if(cerinta==1)
    {
        rez_1();
        return 0;
    }
    if(cerinta==2)
    {
        rez_2();
        return 0;
    }
    rez_3();
    return 0;
}