#include <bits/stdc++.h>
template <typename tp>
inline tp max(tp x, tp y) {
  return (x > y) ? x : y;
}
template <typename tp>
inline tp min(tp x, tp y) {
  return (x < y) ? x : y;
}
template <typename tp>
inline bool chkmax(tp& x, tp y) {
  return (x >= y) ? false : (x = y, true);
}
template <typename tp>
inline bool chkmin(tp& x, tp y) {
  return (x <= y) ? false : (x = y, true);
}
template <typename tp>
tp read(tp& in) {
  in = 0;
  char ch = getchar();
  tp f = 1;
  for (; ch > '9' || ch < '0'; ch = getchar())
    if (ch == '-') f = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) in = in * 10 + ch - '0';
  return in *= f;
}
static const int max1 = 1e5 + 11;
static const int max2 = 2e5 + 11;
int n, m;
int Ct, Ht[max1], Nt[max2], to[max2], dt[max2];
void ins(int x, int y, int z) {
  Nt[++Ct] = Ht[x], Ht[x] = Ct, to[Ct] = y, dt[Ct] = z;
  Nt[++Ct] = Ht[y], Ht[y] = Ct, to[Ct] = x, dt[Ct] = z;
}
int s, rt;
long long ans;
bool V[max1];
int f[max1], size[max1];
void get_root(int x, int fa) {
  size[x] = 1;
  f[x] = 0;
  for (int i = (Ht[x]); i; i = (Nt[i]))
    if (!V[to[i]] && to[i] ^ fa) {
      get_root(to[i], x);
      size[x] += size[to[i]];
      chkmax(f[x], size[to[i]]);
    }
  chkmax(f[x], s - size[x]);
  if (f[x] < f[rt]) rt = x;
}
inline int add(int x, int y) {
  x += y;
  if (x >= m) x -= m;
  return x;
}
inline int reduce(int x, int y) {
  x -= y;
  if (x < 0) x += m;
  return x;
}
inline void Add(int& x, int y) {
  x += y;
  if (x >= m) x -= m;
}
inline void Reduce(int& x, int y) {
  x -= y;
  if (x < 0) x += m;
}
int exgcd(int a, int b, int& x, int& y) {
  if (!b) return x = 1, y = 0, a;
  int res = exgcd(b, a % b, x, y);
  int t = x;
  x = y;
  y = t - (a / b) * y;
  return res;
}
inline int inv(int x, int y) {
  int inv, fk;
  int fl = exgcd(x, y, inv, fk);
  inv = add(inv % m, m);
  return (fl ^ 1) ? -1 : inv;
}
int qpow(int x, int y) {
  int res = 1;
  for (; y; y >>= 1, x = 1LL * x * x % m)
    if (y & 1) res = 1LL * res * x % m;
  return res;
}
std ::map<int, int> ccc;
int d[max1], dpt[max1], seq[3][max1], sq, d1[max1];
void get_d(int x, int fa) {
  ++sq;
  ccc[d[x]]++;
  seq[0][sq] = d[x];
  seq[1][sq] = d1[x];
  seq[2][sq] = qpow(10, dpt[x] + 1);
  for (int i = (Ht[x]); i; i = (Nt[i]))
    if (!V[to[i]] && to[i] ^ fa) {
      dpt[to[i]] = dpt[x] + 1;
      d[to[i]] = add(1LL * dt[i] * qpow(10, dpt[to[i]]) % m, d[x]);
      d1[to[i]] = add(10LL * d1[x] % m, dt[i]);
      get_d(to[i], x);
    }
}
long long calc(int x, int D, int dept) {
  d[x] = d1[x] = D;
  dpt[x] = dept;
  get_d(x, 0);
  long long res = 0LL;
  for (int i = (1), ir = (sq); i <= (ir); ++i) {
    int v = inv(seq[2][i], m);
    if (v == -1) continue;
    res += ccc[1LL * reduce(0, seq[1][i]) * v % m];
    if (1LL * reduce(0, seq[1][i]) * v % m == seq[0][i]) --res;
  }
  while (sq) ccc[seq[0][sq--]]--;
  return res;
}
void solve(int x) {
  ans += calc(x, 0, -1);
  V[x] = true;
  for (int i = (Ht[x]); i; i = (Nt[i]))
    if (!V[to[i]]) {
      ans -= calc(to[i], dt[i], 0);
      s = size[to[i]];
      rt = 0;
      get_root(to[i], 0);
      solve(rt);
    }
}
int main() {
  read(n), read(m);
  for (int i = (1), ir = (n - 1); i <= (ir); ++i) {
    int x, y, z;
    read(x), read(y), read(z);
    ++x;
    ++y;
    z %= m;
    ins(x, y, z);
  }
  s = n;
  f[0] = n;
  get_root(1, 0);
  solve(rt);
  printf("%I64d\n", ans);
  return 0;
}
