#include <bits/stdc++.h>
using namespace std;
long long n, M;
const long long MX = 101111;
struct edge {
  long long to, w;
};
vector<edge> g[MX];
long long ni10[MX], z10[MX];
namespace Niyuan {
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0 && b == 0) return -1;
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extend_gcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
long long mod_r(long long a, long long n) {
  long long x, y;
  long long d = extend_gcd(a, n, x, y);
  if (d == 1)
    return (x % n + n) % n;
  else
    return -1;
}
}  // namespace Niyuan
long long wt[MX];
long long del[MX];
long long newroot;
long long maxn = 0x3f3f3f3f;
long long dfs(long long now, long long fa, long long all, long long &newroot,
              long long dep) {
  wt[now] = 1;
  long long mx = 0;
  for (long long i = 0; i < g[now].size(); i++) {
    long long to = g[now][i].to;
    if (to == fa || del[to]) continue;
    long long siz = dfs(to, now, all, newroot, dep + 1);
    mx = max(mx, siz);
    wt[now] += siz;
  }
  mx = max(mx, all - wt[now]);
  if (mx < maxn) maxn = mx, newroot = now;
  return wt[now];
}
long long searchit(long long root, long long all) {
  maxn = 0x3f3f3f3f;
  dfs(root, -1, all, newroot, 1);
  return newroot;
}
map<long long, long long> mp;
long long ans = 0;
long long tque[101111];
long long tl = 0;
void gao(long long u, long long fa, long long zv, long long fv, long long dep,
         long long sef) {
  long long cha = (((-zv * ni10[dep]) % M + M) % M);
  if (mp.count(cha)) ans += mp[cha];
  if (zv == 0 && sef) {
    ans++;
  }
  if (fv == 0 && sef) {
    ans++;
  }
  if (fa != -1) {
    tque[tl++] = fv;
  }
  for (long long i = 0; i < g[u].size(); i++) {
    long long to = g[u][i].to;
    if (to == fa || del[to]) continue;
    long long w = g[u][i].w;
    long long nzv = (((zv * 10 + w) % M + M) % M);
    long long nfv = (((w * z10[dep] + fv) % M + M) % M);
    gao(to, u, nzv, nfv, dep + 1, sef);
  }
}
void fz(long long rt, long long sz) {
  queue<pair<int, int> > sq;
  sq.push(make_pair((rt), (sz)));
  while (!sq.empty()) {
    pair<int, int> now = sq.front();
    sq.pop();
    long long nr = searchit(now.first, now.second);
    del[nr] = true;
    mp.clear();
    for (long long i = 0; i < g[nr].size(); i++) {
      long long to = g[nr][i].to;
      if (del[to]) continue;
      long long w = g[nr][i].w % M;
      tl = 0;
      gao(to, nr, w, w, 1, 1);
      for (long long j = 0; j < tl; j++) {
        mp[tque[j]]++;
      }
      sq.push(make_pair((to), (wt[to])));
    }
    long long gsz = g[nr].size();
    mp.clear();
    for (long long i = gsz - 1; i >= 0; i--) {
      long long to = g[nr][i].to;
      if (del[to]) continue;
      long long w = g[nr][i].w % M;
      tl = 0;
      gao(to, nr, w, w, 1, 0);
      for (long long j = 0; j < tl; j++) {
        mp[tque[j]]++;
      }
    }
  }
}
int main() {
  scanf("%I64d%I64d", &n, &M);
  ni10[0] = 1;
  z10[0] = 1;
  long long nn10 = Niyuan::mod_r(10, M);
  for (long long i = 1; i < MX; i++) {
    ni10[i] = ni10[i - 1] * nn10 % M;
    z10[i] = z10[i - 1] * 10 % M;
  }
  for (long long i = 0; i < n - 1; i++) {
    long long u, v, w;
    scanf("%I64d%I64d%I64d", &u, &v, &w);
    g[u].push_back((edge){v, w});
    g[v].push_back((edge){u, w});
  }
  fz(0, n);
  cout << ans << endl;
  return 0;
}
