#include <bits/stdc++.h>
using namespace std;
void Rd(int &res) {
  res = 0;
  char p;
  while (p = getchar(), p < '0')
    ;
  do {
    res = (res * 10) + (p ^ 48);
  } while (p = getchar(), p >= '0');
}
struct W {
  int to, nx, d;
} Lis[100005 << 1];
int Head[100005], tot = 1;
void Add(int x, int y, int d) {
  Lis[tot].to = y, Lis[tot].nx = Head[x], Lis[tot].d = d;
  Head[x] = tot++;
}
map<int, int> mp, pm;
int n, P, phi, cntson[100005], Mxson[100005], pro[100005], por[100005],
    de[100005], L[100005], R[100005], dfs_cnt, dui[100005];
int fs[100005 * 2];
long long ans = 0;
int fast(int x, int p) {
  int re = 1;
  while (p) {
    if (p & 1) re = (long long)re * x % P;
    x = (long long)x * x % P, p >>= 1;
  }
  return re;
}
void dfs_pre(int x, int f, int v1, int c, int v2, int fac) {
  dui[L[x] = ++dfs_cnt] = x;
  cntson[x] = 1;
  pro[x] = v1, por[x] = v2;
  de[x] = c;
  int Mx = 0;
  for (int i = Head[x], to; i && (to = Lis[i].to, 1); i = Lis[i].nx)
    if (to != f) {
      dfs_pre(to, x, (v1 * 10LL + Lis[i].d) % P, c + 1,
              (v2 + (long long)fac * Lis[i].d) % P, fac * 10LL % P);
      cntson[x] += cntson[to];
      if (cntson[to] > Mx) Mx = cntson[to], Mxson[x] = to;
    }
  R[x] = dfs_cnt;
}
int POP(int x) { return fs[x + 100005]; }
void upd(int p, int f) {
  map<int, int>::iterator it;
  int pa;
  pa = (por[f] + (long long)pro[f] * POP(de[f]) % P -
        (long long)pro[p] * POP(2 * de[f] - de[p]) % P) %
       P;
  pa = (pa + P) % P;
  it = pm.find(pa);
  if (it != pm.end()) ans += (it->second);
  pa = ((long long)pro[f] * POP(-de[f]) % P +
        (long long)(por[f] - por[p]) * POP(-de[f]) % P * POP(-de[f]) % P) %
       P;
  pa = (pa + P) % P;
  it = mp.find(pa);
  if (it != mp.end()) ans += (it->second);
}
void dfs_pls(int x, int f) {
  for (int i = L[x]; i <= R[x]; i++) upd(dui[i], f);
}
void dfs_add(int x) {
  for (int i = L[x]; i <= R[x]; i++) {
    int p = dui[i];
    int pa = (long long)pro[p] * POP(-de[p]) % P;
    mp[pa]++, pm[por[p]]++;
  }
}
void dfs_sol(int x, int f) {
  int pa;
  if (Mxson[x]) {
    for (int i = Head[x], to; i && (to = Lis[i].to, 1); i = Lis[i].nx)
      if (to != f && to != Mxson[x]) dfs_sol(to, x), mp.clear(), pm.clear();
    dfs_sol(Mxson[x], x);
    for (int i = Head[x], to; i && (to = Lis[i].to, 1); i = Lis[i].nx)
      if (to != f && to != Mxson[x]) dfs_pls(to, x), dfs_add(to);
    upd(x, x);
  }
  pa = (long long)pro[x] * POP(-de[x]) % P;
  mp[pa]++, pm[por[x]]++;
}
int main() {
  Rd(n), Rd(P);
  if (P == 1) {
    cout << (long long)n * (n - 1) << endl;
    return 0;
  }
  int t = P;
  phi = P;
  for (int i = 2; (long long)i * i <= t; i++)
    if (t % i == 0) {
      phi = phi / i * (i - 1);
      while (t % i == 0) t /= i;
    }
  if (t > 1) phi = phi / t * (t - 1);
  phi--;
  fs[100005] = 1;
  int inv = fast(10, phi);
  for (int i = 1; i <= n; i++) fs[i + 100005] = fs[i + 100005 - 1] * 10LL % P;
  for (int i = 1; i <= n; i++)
    fs[100005 - i] = (long long)fs[100005 - i + 1] * inv % P;
  for (int i = 1, x, y, d; i < n; i++)
    Rd(x), Rd(y), Rd(d), x++, y++, Add(x, y, d), Add(y, x, d);
  dfs_pre(1, 1, 0, 0, 0, 1);
  dfs_sol(1, 1);
  cout << ans << endl;
  return 0;
}
