#include <bits/stdc++.h>

using namespace std;

const int N = 1<<17;
const int LOG = 18;

vector < int > v[N],digit[N];

namespace cd {
    int sz[N];
    bool used[N];
    int parent[N];
    int link[N];
    #define cd_parent parent
    void cd_dfs(int node, vector < int > &path) {
        used[node]=true;
        path.push_back(node);
        sz[node]=1;
        int i;
        for(i=0;i<(int)(v[node].size());i++) if(!used[v[node][i]]) {
            cd_dfs(v[node][i],path);
            sz[node]+=sz[v[node][i]];
        }
    }

    int get_centroid(int node, int cnt) {
        int i,max_size=-1,who;
        used[node]=true;
        for(i=0;i<(int)(v[node].size());i++) if(!used[v[node][i]]) {
            if(sz[v[node][i]]>max_size) max_size=sz[v[node][i]],who=v[node][i];
        }
        if(max_size<=(cnt>>1)) return node;
        else return get_centroid(who,cnt);
    }

    int centroid_decomposition(int node) {
        int i,ans;
        vector < int > nodes;
        cd_dfs(node,nodes);
        for(i=0;i<(int)(nodes.size());i++) used[nodes[i]]=false;
        ans=get_centroid(node,(int)(nodes.size()));
        for(i=0;i<(int)(nodes.size());i++) used[nodes[i]]=false;
        used[ans]=true;
        for(i=0;i<(int)(v[ans].size());i++) if(!used[v[ans][i]]) cd_parent[centroid_decomposition(v[ans][i])]=ans;
        return ans;
    }
}

#define pow oaighkjqghja
#define pow10 pow

int n,m;
int pow[N];
map < int, int > cnt[N];
map < pair < int, int >, int > cnt2[N];
long long ans;
int root;
bool used[N];
int parent[N],level[N];
int link[N];
int jump[N][LOG];
int jump_value[N][LOG];
int partial_reversed_value[N];

int fpow(int a, int b) {
    if(a==0) return 0;
    if(b==0) return 1;
    int p=fpow(a,b>>1);
    p=(p*1ll*p)%m;
    if(b&1) p=(p*1ll*a)%m;
    return p;
}

int div_mod(int a, int b) {
    return (a*1ll*fpow(b,m-2))%m;
}

void dfs(int node) {
    partial_reversed_value[node]=(partial_reversed_value[parent[node]]*1ll*10)%m;
    partial_reversed_value[node]=(partial_reversed_value[node]+link[node])%m;
    used[node]=true;
    int i;
    for(i=0;i<(int)(v[node].size());i++) if(!used[v[node][i]]) parent[v[node][i]]=node,level[v[node][i]]=level[node]+1,link[v[node][i]]=digit[node][i],dfs(v[node][i]);
}

int walk_up(int node, int lvl) {
    int i;
    for(i=16;i>=0;i--) if(jump[node][i]>=lvl) node=jump[node][i];
    return node;
}

int get_lca(int a, int b) {
    if(level[a]>level[b]) swap(a,b);
    b=walk_up(b,level[a]);
    if(a==b) return a;
    int i;
    for(i=16;i>=0;i--) if(jump[a][i]!=jump[b][i]) a=jump[a][i],b=jump[b][i];
    return parent[a];
}

int get_distance(int a, int b) {
    return level[a]+level[b]-(level[get_lca(a,b)]<<1);
}

int get_jump_value(int a, int b) {
    int ans=0,i;
    for(i=16;i>=0;i--) {
        if(level[jump[a][i]]>=level[b]) {
            ans=(ans*1ll*pow[1<<i])%m;
            ans=(ans+jump_value[a][i])%m;
            a=jump[a][i];
        }
    }
    return ans;
}

int get_reversed_value(int a, int b) {
    int ans=(partial_reversed_value[a]-(pow[level[a]-level[b]]*1ll*partial_reversed_value[b])%m+m)%m;
    //ans=div_mod(ans,pow[level[b]-level[a]]);
    return ans;
}

int get_value(int a, int b) {
    int their_lca=get_lca(a,b),dist1=level[a]-level[their_lca],dist2=level[b]-level[their_lca],ans;
    ans=(get_jump_value(a,their_lca)*1ll*pow[dist2])%m;
    ans=(ans+get_reversed_value(b,their_lca))%m;
    return ans;
}

void update(int node) {
    int value,from=-1,where=node;
    while(where) {
        value=get_value(node,where);
        ++cnt[where][value];
        ++cnt2[where][make_pair(value,from)];
        from=where;
        where=cd::parent[where];
    }
}

int query(int node) {
    int value,ans=0,length,need,from=-1,where=node;
    while(where) {
        value=get_value(where,node);
        need=(0-value+m)%m;
        length=get_distance(where,node);
        need=div_mod(need,pow[length]);
        ans+=cnt[where][need]-cnt2[where][make_pair(need,from)];
        from=where;
        where=cd::parent[where];
    }
    return ans;
}

int main() {
    int i,j,x,y,z;

    scanf("%d %d", &n, &m);
    pow[0]=1;
    for(i=1;i<N;i++) pow[i]=(pow[i-1]*1ll*10)%m;
    for(i=1;i<n;i++) scanf("%d %d %d", &x, &y, &z),++x,++y,v[x].push_back(y),v[y].push_back(x),digit[x].push_back(z),digit[y].push_back(z);
    level[1]=1;
    dfs(1);
    for(i=1;i<=n;i++) jump[i][0]=parent[i],jump_value[i][0]=link[i];
    for(j=1;j<=16;j++) for(i=1;i<=n;i++) {
        jump[i][j]=jump[jump[i][j-1]][j-1];
        jump_value[i][j]=jump_value[i][j-1];
        jump_value[i][j]=(jump_value[i][j]*1ll*pow[1<<(j-1)])%m;
        jump_value[i][j]=(jump_value[i][j]+jump_value[jump[i][j-1]][j-1])%m;
    }
    root=cd::centroid_decomposition(1);
    for(i=1;i<=n;i++) update(i);
    for(i=1;i<=n;i++) ans+=query(i);
    printf("%lld\n", ans);

    return 0;
}