#include<bits/stdc++.h>

using namespace std;

#define N 1005

#define INF 1147483647//2^31-1-10^9

#define T 5

vector<int> v[N];

int n,m,root,dp[N][5],ans;

string s[N];//{'@',0} 負責記錄變化最少的結果

map<char,int> mp={{'@',0},{'A',1},{'U',2},{'C',3},{'G',4}};//A、U、C、G

void Virus(int f,int pos){

    int b=mp[s[f][pos]];// 紀錄符號

    if(v[f].empty()){

        if(s[f][pos]=='@') return;

        for(int i=1;i<T;i++)

            dp[f][i]=INF;

        dp[f][0]=dp[f][b]=0;

        return;

    } 

    for(auto e:v[f])

        Virus(e,pos);

    if(s[f][pos]=='@'){// 因為是 @所以每種變化都計算一遍

        for(int i=1;i<T;i++)

            for(auto e:v[f])

                dp[f][i]+=min(dp[e][0]+1,dp[e][i]);

        dp[f][0]=min(min(dp[f][1],dp[f][2]),min(dp[f][3],dp[f][4]));

    }else{

        for(int i=1;i<T;i++) dp[f][i]=INF;

        dp[f][b]=0;

        for(auto e:v[f])

            dp[f][b]+=min(dp[e][0]+1,dp[e][b]);// 一樣的不用加 1

        dp[f][0]=dp[f][b];

    }

}

int main(){

    cin>>n>>m;

    for(int i=0,a,b;i<n;i++){

        cin>>a>>b;

        cin>>s[a];

        if(a==b) root=a;

        else v[b].push_back(a);

    }

    for(int i=0;i<m;i++){

        Virus(root,i);

        ans+=dp[root][0];

        memset(dp,0,sizeof(dp));

    }

    cout<<ans;

}