挖坑：CF712E

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 1000005

using namespace std;

int n,m,tot,sum,root,top,stack[maxn][2],h[maxn],way[maxn*2],Next[maxn*2],w[maxn*2],size[maxn],power_10[maxn],ni[maxn];

long long ans;

bool v[maxn];

int read(){

	int x=0,f=1;char ch;

	for(ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct Hash{

	#define mod 555616

	int cnt,head[mod],fuck[maxn],val[maxn],num[maxn];

	void clear(int x){head[x%mod]=0;}

	void insert(int x){

		for(int i=head[x%mod];i;i=fuck[i])if(val[i]==x){num[i]++;return;}

		++cnt;val[cnt]=x;fuck[cnt]=head[x%mod];head[x%mod]=cnt;num[cnt]=1;

	}

	int find(int x){

		for(int i=head[x%mod];i;i=fuck[i])if(val[i]==x)return num[i];

		return 0;

	}

}hash;

void insert(int x,int y,int z){way[++tot]=y;Next[tot]=h[x];h[x]=tot;w[tot]=z;}

void exgcd(int a,int b,int &x,int &y){

	if(b==0){x=1;y=0;return;}

	int tx,ty;exgcd(b,a%b,tx,ty);

	x=ty;y=tx-a/b*ty;

}

int getni(){

	int x,y;exgcd(10,m,x,y);

	x=(x%m+m)%m;return x;

}

void getroot(int x,int fa){

	size[x]=1;int pps=0;

	for(int j=h[x];j;j=Next[j])if(way[j]!=fa&&!v[way[j]]){

		getroot(way[j],x);size[x]+=size[way[j]];pps=max(pps,size[way[j]]);

	}

	if(max(pps,sum-size[x])<=sum/2)root=x;

}

void reverse(){for(int i=1;i<=top/2;i++)swap(stack[i][0],stack[top-i+1][0]),swap(stack[i][1],stack[top-i+1][1]);}

void calc(int x,int fa,int len,int num){

	ans+=hash.find((1LL*(-num)*ni[len]%m+m)%m);

	for(int j=h[x];j;j=Next[j])if(way[j]!=fa&&!v[way[j]])calc(way[j],x,len+1,(1LL*num*10+w[j])%m);

}

void change(int x,int fa,int len,int num,int op){

	if(op)hash.insert(num);else hash.clear(num);

	for(int j=h[x];j;j=Next[j])if(way[j]!=fa&&!v[way[j]])change(way[j],x,len+1,(1LL*w[j]*power_10[len]+num)%m,op);

}

void calc(int x,int op){

	if(op)hash.insert(0);

	for(int i=1;i<=top;i++)calc(stack[i][0],x,1,stack[i][1]),change(stack[i][0],x,1,stack[i][1],1);

	if(op)ans+=hash.find(0)-1,hash.clear(0);

	for(int i=1;i<=top;i++)change(stack[i][0],x,1,stack[i][1],0);

}

void work(int x,int s){

	top=0;v[x]=1;

	for(int j=h[x];j;j=Next[j])if(!v[way[j]])++top,stack[top][0]=way[j],stack[top][1]=w[j];

	calc(x,1);reverse();calc(x,0);

	for(int j=h[x];j;j=Next[j])if(!v[way[j]]){

		sum=size[way[j]]>size[x]?s-size[x]:size[way[j]];

		getroot(way[j],x);work(root,sum);

	}

}

int main(){

	n=read();m=read();

	power_10[0]=ni[0]=1;

	for(int i=1,j=getni();i<=n;i++)power_10[i]=1LL*power_10[i-1]*10%m,ni[i]=1LL*ni[i-1]*j%m;

	for(int i=1,x,y,z;i<n;i++){

		x=read();y=read();z=read()%m;

		insert(x,y,z);insert(y,x,z);

	}

	sum=n;getroot(0,-1);work(root,sum);

	printf("%lld\n",ans);

	return 0;

}