#include <bits/stdc++.h>
using namespace std;
struct R {
  long long to, val, nex;
} r[520233 << 1];
long long n, m, hea[520233], cnt = 1, siz[520233], die[520233], ans = 0,
                             ny[520233], zy[520233];
long long f[233], x, y;
void K(long long a, long long b) {
  if (b == 1) {
    x = 0;
    y = 1;
    return;
  }
  K(b, a % b);
  swap(x, y);
  y = y - a / b * x;
  return;
}
long long vv[520233], g = 0;
long long mp[1000007 << 1], val[1000007 << 1];
long long has(long long v) {
  long long t = v % 1000007;
  while (val[t] != 0 && val[t] != v) t++;
  val[t] = v;
  vv[++g] = t;
  return t;
}
void P() {
  ny[0] = zy[0] = 1;
  for (long long i = 1; i <= 100002; i++) zy[i] = zy[i - 1] * 10 % m;
  for (long long i = 1; i <= 100002; i++) {
    K(zy[i], m);
    ny[i] = (x % m + m) % m;
  }
  return;
}
void A(long long x, long long fa, long long dep, long long v) {
  mp[has(v)]++;
  for (long long i = hea[x]; i > 0; i = r[i].nex) {
    if (r[i].to == fa || die[r[i].to]) continue;
    A(r[i].to, x, dep + 1, (r[i].val * zy[dep] + v) % m);
  }
  return;
}
long long B(long long x, long long fa, long long dep, long long v) {
  long long turn = mp[has(((-v) % m + m) * ny[dep] % m)];
  for (long long i = hea[x]; i > 0; i = r[i].nex) {
    if (r[i].to == fa || die[r[i].to]) continue;
    turn += B(r[i].to, x, dep + 1, (v * 10 + r[i].val) % m);
  }
  return turn;
}
long long C(long long x, long long stdep, long long v) {
  for (int i = 1; i <= g; i++) mp[vv[i]] = val[vv[i]] = 0;
  g = 0;
  A(x, -1, stdep, v);
  return B(x, -1, stdep, v);
}
void S(long long x, long long fa) {
  siz[x] = 1;
  for (long long i = hea[x]; i > 0; i = r[i].nex) {
    if (r[i].to == fa || die[r[i].to]) continue;
    S(r[i].to, x);
    siz[x] += siz[r[i].to];
  }
  return;
}
long long H(long long x, long long fa, long long totsiz) {
  for (long long i = hea[x]; i > 0; i = r[i].nex)
    if (siz[r[i].to] * 2 > totsiz && !die[r[i].to] && r[i].to != fa)
      return H(r[i].to, x, totsiz);
  return x;
}
void D(long long x, long long fa) {
  die[x] = 1;
  ans += C(x, 0, 0);
  for (long long i = hea[x]; i > 0; i = r[i].nex) {
    if (r[i].to == fa || die[r[i].to]) continue;
    ans -= C(r[i].to, 1, r[i].val);
    S(r[i].to, -1);
    D(H(r[i].to, -1, siz[r[i].to]), x);
  }
}
int main() {
  scanf("%I64d%I64d", &n, &m);
  P();
  long long u, v, w;
  for (long long i = 1; i < n; i++) {
    scanf("%I64d%I64d%I64d", &u, &v, &w);
    w %= m;
    r[++cnt] = (R){v, w, hea[u]};
    hea[u] = cnt;
    r[++cnt] = (R){u, w, hea[v]};
    hea[v] = cnt;
  }
  S(0, -1);
  D(H(0, -1, siz[0]), -1);
  ans -= n;
  cout << ans;
}
