#include<cstdio>#include<cstring>#include<algorithm>#define maxn 1000005using 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;}