#include <bits/stdc++.h>
using namespace std;
int n, Mod, p[100010], a[200010], nxt[200010], w[200010], tot, root,
    size[100010], son[100010], cnt;
bool vis[100010];
long long ans, mul[100010];
struct record {
  int dep, step;
  record(int D = 0, int S = 0) {
    dep = D;
    step = S;
  }
} pre[100010], suf[100010];
int comp(record a, record b) { return a.dep < b.dep; }
void add(int x, int y, int val) {
  tot++;
  a[tot] = y;
  nxt[tot] = p[x];
  w[tot] = val;
  p[x] = tot;
}
void getroot(int u, int fa, int N) {
  size[u] = 1;
  son[u] = 0;
  for (int i = p[u]; i != 0; i = nxt[i])
    if (a[i] != fa && vis[a[i]] == false) {
      getroot(a[i], u, N);
      size[u] += size[a[i]];
      son[u] = max(son[u], size[a[i]]);
    }
  son[u] = max(son[u], N - size[u]);
  if (son[u] < son[root]) root = u;
}
void getdeep(int u, int fa, long long pred, int step, long long sufd) {
  pre[++cnt] = record(pred, step);
  suf[cnt] = record(sufd, step);
  for (int i = p[u]; i != 0; i = nxt[i])
    if (a[i] != fa && vis[a[i]] == false)
      getdeep(a[i], u, (pred * 10 + w[i]) % Mod, step + 1,
              (sufd + w[i] * mul[step] % Mod) % Mod);
}
int findL(int l, int r, int x, record *v) {
  int mid;
  while (l != r) {
    mid = (l + r) >> 1;
    if (v[mid].dep >= x)
      r = mid;
    else
      l = mid + 1;
  }
  if (v[l].dep != x) return 1000000000;
  return l;
}
int findR(int l, int r, int x, record *v) {
  int mid, ans = 0;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (v[mid].dep <= x) {
      ans = max(ans, mid);
      l = mid + 1;
    } else
      r = mid - 1;
  }
  if (v[ans].dep != x) return 0;
  return ans;
}
long long getnum(int l, int r, int now, record *v) {
  int L, R;
  if (l > r) return 0;
  L = findL(l, r, now, v);
  R = findR(l, r, now, v);
  if (L <= R) return R - L + 1;
  return 0;
}
void exgcd(int a, int b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  long long t;
  exgcd(b, a % b, x, y);
  t = x;
  x = y;
  y = t - (a / b) * y;
}
int getinv(long long A, long long B) {
  long long x, y;
  exgcd(A, Mod, x, y);
  x = (x % Mod + Mod) % Mod;
  x = (x * B) % Mod;
  return x;
}
long long calc(int u, int pre0, int s0, int suf0) {
  long long sum = 0;
  cnt = 0;
  getdeep(u, 0, pre0, s0, suf0);
  sort(pre + 1, pre + cnt + 1, comp);
  sort(suf + 1, suf + cnt + 1, comp);
  for (int i = 1; i <= cnt; i++) {
    int now = getinv(mul[pre[i].step], Mod - pre[i].dep);
    sum += getnum(1, cnt, now, suf);
    if (now == 0) --sum;
  }
  return sum;
}
void work(int u) {
  ans += calc(u, 0, 0, 0);
  vis[u] = true;
  for (int i = p[u]; i != 0; i = nxt[i])
    if (vis[a[i]] == false) {
      ans -= calc(a[i], w[i] % Mod, 1, w[i] % Mod);
      root = 0;
      getroot(a[i], 0, size[a[i]]);
      work(root);
    }
}
int main() {
  scanf("%d%d", &n, &Mod);
  for (int i = 1; i < n; i++) {
    int x, y, v;
    scanf("%d%d%d", &x, &y, &v);
    ++x;
    ++y;
    add(x, y, v);
    add(y, x, v);
  }
  son[0] = 1000000000;
  root = 0;
  mul[0] = 1;
  for (int i = 1; i <= n; i++) mul[i] = mul[i - 1] * 10 % Mod;
  getroot(1, 0, n);
  work(root);
  printf("%I64d\n", ans);
  return 0;
}
