#include <bits/stdc++.h>
using namespace std;
const long long N = 100005, inf = 0x3f3f3f3f;
struct node {
  long long y, z, nxt;
} e[N * 2];
long long ans;
long long sm, h[N], c = 1, vis[N], d[N], siz[N], mx[N];
long long rt, n, m, pw[N], tot, dis[N];
map<long long, long long> mp;
void add(long long x, long long y, long long z) {
  e[++c] = (node){y, z, h[x]};
  h[x] = c;
  e[++c] = (node){x, z, h[y]};
  h[y] = c;
}
void getrt(long long x, long long fa) {
  siz[x] = 1;
  mx[x] = 0;
  for (long long i = h[x], y; i; i = e[i].nxt)
    if ((y = e[i].y) != fa && !vis[y]) {
      getrt(y, x);
      siz[x] += siz[y];
      mx[x] = max(mx[x], siz[y]);
    }
  mx[x] = max(mx[x], sm - siz[x]);
  if (mx[x] < mx[rt]) rt = x;
  return;
}
void exgcd(long long a, long long b, long long &d, long long &x, long long &y) {
  if (!b)
    d = a, x = 1, y = 0;
  else
    exgcd(b, a % b, d, y, x), y -= x * (a / b);
}
long long inv(long long a, long long p) {
  long long x, y, d;
  exgcd(a, p, d, x, y);
  return d == 1 ? (x % p + p) % p : -1;
}
void dfs(long long x, long long fa, long long v1, long long v2, long long dep) {
  if (dep) {
    mp[v2 % m]++;
    dis[++tot] = v1;
    d[tot] = dep;
  }
  for (long long i = h[x], y; i; i = e[i].nxt)
    if ((y = e[i].y) != fa && !vis[y]) {
      dfs(y, x, (v1 * 10 % m + e[i].z) % m, (v2 + e[i].z * pw[dep] % m) % m,
          dep + 1);
    }
  return;
}
long long calc(long long x, long long v, long long op) {
  long long res = 0;
  tot = 0;
  mp.clear();
  dfs(x, 0, v, v, op);
  for (long long i = 1; i <= tot; i++) {
    long long val = (m - dis[i] * inv(pw[d[i]], m) % m) % m;
    if (mp.find(val) != mp.end()) res += mp[val];
    if (!op) res += (dis[i] == 0);
  }
  if (!op) res += mp[0];
  return res;
}
void solve(long long x) {
  ans += calc(x, 0, 0);
  vis[x] = 1;
  for (long long i = h[x], y; i; i = e[i].nxt)
    if (!vis[y = e[i].y]) {
      ans -= calc(y, e[i].z, 1);
      mx[rt = 0] = inf;
      sm = siz[y];
      getrt(y, 0);
      solve(rt);
    }
  return;
}
signed main() {
  scanf("%lld%lld", &n, &m);
  for (long long i = 1, x, y, z; i < n; i++)
    scanf("%lld%lld%lld", &x, &y, &z), add(x + 1, y + 1, z);
  pw[0] = 1;
  for (long long i = 1; i <= n; i++) pw[i] = 1ll * pw[i - 1] * 10 % m;
  mx[rt] = inf;
  sm = n;
  getrt(1, 0);
  solve(rt);
  printf("%lld\n", ans);
  return 0;
}
