rt，用的是淀粉质

#include<bits/stdc++.h> 
using namespace std;
const int N = 1e5 + 5;
#define int long long
int n,m;
int exgcd(int &x,int &y,int a,int b){
	if(a % b == 0) return x = 0,y = 1,b;
	int g = exgcd(y,x,b,a%b);
	return y -= a/b,g;
}
int iv[N],pw[N];
vector<pair<int,int> > G[N];
map<int,int> M;
int sz[N],rt = -1;
bool del[N];
void Fin(int x,int fa){
	int mxs = 0;
	sz[x] = 1;
	for(auto nxt:G[x]){
		int y = nxt.first;
		if(y == fa || del[y]) continue;
		Fin(y,x);
		if(rt != -1) return ;
		sz[x] += sz[y],mxs = max(mxs,sz[y]);
	}
	mxs = max(mxs,n - sz[x]);
	if(mxs <= (n >> 1))
		sz[fa] = n - sz[x],rt = x;
	return ;
}
int st[N],tp,ans;
void Cal(int x,int fa,int a,int b,int cnt){
	int l = (m - a * iv[cnt] % m) % m;
	if(l == 0) ++ ans;
	ans += M[l],st[++ tp] = b;
	for(auto nxt:G[x]){
		int y = nxt.first,w = nxt.second;
		if(y == fa || del[y]) continue;
		Cal(y,x,(a * 10 + w) % m,(b + w * pw[cnt] % m) % m,cnt + 1);
	}
}
void Sol(int x){
	for(auto nxt:G[x]){
		int y = nxt.first,w = nxt.second;
		if(del[y]) continue;
		Cal(y,x,w,w,1);
		while(tp) ++ M[st[tp --]];
	}
	reverse(G[x].begin(),G[x].end()),M.clear();
	for(auto nxt:G[x]){
		int y = nxt.first,w = nxt.second;
		if(del[y]) continue;
		Cal(y,x,w,w,1);
		while(tp) ++ M[st[tp --]];
	}
	del[x] = 1,M.clear();
	for(auto nxt:G[x]){
		int y = nxt.first,w = nxt.second;
		if(del[y]) continue;
		n = sz[y],rt = -1,Fin(y,0),Sol(rt);
	}
}
signed main(){
	cin >> n >> m;
	for(int i = 1,x,y,w;i < n;i ++){
		cin >> x >> y >> w;
		++ x, ++ y;
		G[x].push_back({y,w});
		G[y].push_back({x,w});
	}
	int x,y;
	exgcd(x,y,10,m);
	x = (x % m + m) % m;
	iv[0] = pw[0] = 1;
	for(int i = 1;i <= n;i ++)
		iv[i] = iv[i - 1] * x % m,
		pw[i] = pw[i - 1] * 10 % m;
	rt = -1,Fin(1,0),Sol(rt);
//	cout << rt << '\n';
	cout << ans << '\n';
	return 0;
}