#include <bits/stdc++.h>
using namespace std;
vector<long long> ed[100010], cost[100010];
long long ans;
long long sz[100010], m;
long long tp[100011];
bool done[100010];
map<long long, long long> downf, upf, downfl[100010], upfl[100010];
void dfs(long long n, long long p) {
  sz[n] = 1;
  for (long long i = 0; i < ed[n].size(); i++) {
    long long v = ed[n][i];
    if (v != p && done[v] == false) {
      dfs(v, n);
      sz[n] += sz[v];
    }
  }
}
long long s2, s1, t2, t1;
long long egcd(long long a, long long b) {
  long long temp;
  if (a % b == 0) {
    return s1;
  }
  temp = s2 - (a / b) * s1;
  s2 = s1;
  s1 = temp;
  temp = t2 - (a / b) * t1;
  t2 = t1;
  t1 = temp;
  return egcd(b, a % b);
}
void ndfs(long long n, long long p, long long loc, long long down,
          long long h) {
  long long x = (-down) % m;
  if (x < 0) x += m;
  long long y = tp[h];
  s2 = t1 = 1;
  s1 = t2 = 0;
  y = (egcd(y, m) % m + m) % m;
  x = (x * y) % m;
  ans += upf[x] - upfl[loc][x];
  for (long long i = 0; i < ed[n].size(); i++) {
    long long v = ed[n][i];
    if (v != p && done[v] == false) {
      ndfs(v, n, loc, ((down * 10) % m + cost[n][i]) % m, h + 1);
    }
  }
}
void adfs(long long n, long long p, long long loc, long long down, long long up,
          long long h) {
  downf[down]++;
  upf[up]++;
  downfl[loc][down]++;
  upfl[loc][up]++;
  if (!(up % m)) ans++;
  for (long long i = 0; i < ed[n].size(); i++) {
    long long v = ed[n][i];
    if (v != p && done[v] == false) {
      adfs(v, n, loc, ((down * 10) % m + cost[n][i]) % m,
           (up + ((tp[h] * cost[n][i]) % m)) % m, h + 1);
    }
  }
}
long long decompose(long long cen) {
  dfs(cen, -1);
  long long target = sz[cen] / 2, p = -1;
  bool ok = false;
  while (!ok) {
    ok = true;
    for (long long i = 0; i < ed[cen].size(); i++) {
      long long v = ed[cen][i];
      if (p != v && done[v] == false && sz[v] > target) {
        ok = false;
        p = cen;
        cen = v;
      }
    }
  }
  done[cen] = true;
  downf.clear();
  upf.clear();
  upf[0]++;
  for (long long i = 0; i < ed[cen].size(); i++) {
    long long v = ed[cen][i];
    upfl[v].clear();
    downfl[v].clear();
    if (!done[v]) {
      adfs(v, cen, v, cost[cen][i] % m, cost[cen][i] % m, 1);
    }
  }
  for (long long i = 0; i < ed[cen].size(); i++) {
    long long v = ed[cen][i];
    if (!done[v]) {
      ndfs(v, cen, v, cost[cen][i] % m, 1);
    }
  }
  for (long long i = 0; i < ed[cen].size(); i++) {
    long long v = ed[cen][i];
    if (!done[v]) {
      decompose(v);
    }
  }
  return cen;
}
int main() {
  long long cs, ts, i, j, k, x, y, z, q, n;
  tp[0] = 1;
  scanf("%lld", &n);
  scanf("%lld", &m);
  for (long long i = 1; i <= n; i++) tp[i] = (10 * tp[i - 1]) % m;
  for (i = 1; i < n; i++) {
    scanf("%lld", &x);
    scanf("%lld", &y);
    scanf("%lld", &z);
    x++;
    y++;
    ed[x].push_back(y);
    ed[y].push_back(x);
    cost[x].push_back(z);
    cost[y].push_back(z);
  }
  ans = 0;
  decompose(1);
  printf("%lld\n", ans);
  return 0;
}
