#include <bits/stdc++.h>
int n, M;
long long pow1[100010], pow2[100010], ans;
struct edge {
  int to, w;
  edge* next;
} E[200010], *ne = E, *first[100010];
void link(int u, int v, int w) {
  *ne = (edge){v, w, first[u]};
  first[u] = ne++;
}
int Q[100010], fa[100010], siz[100010], fr[100010], dep[100010], D1[100010],
    D2[100010], L[100010];
bool vis[100010];
long long inv(int a, int p) {
  return a == 1 ? 1 : (1 + p * (a - inv(p % a, a))) / a % p;
}
bool cmp1(int i, int j) {
  return D1[i] < D1[j] || D1[i] == D1[j] && fr[i] < fr[j];
}
bool cmp2(int i, int j) {
  return D2[i] < D2[j] || D2[i] == D2[j] && fr[i] < fr[j];
}
void solve(int root) {
  int head = 0, tail = 1, x = Q[0] = root, g = 0;
  fa[x] = -1;
  siz[x] = 1;
  for (; head < tail; x = Q[++head])
    for (edge* e = first[x]; e; e = e->next)
      if (!vis[e->to] && e->to != fa[x])
        fa[Q[tail++] = e->to] = x, siz[e->to] = 1;
  while (head--) {
    if (fa[x = Q[head]] != -1) siz[fa[x]] += siz[x];
    bool isg = tail - siz[x] <= tail / 2;
    for (edge* e = first[x]; e; e = e->next)
      if (!vis[e->to] && e->to != fa[x])
        if (siz[e->to] > tail / 2) isg = 0;
    if (isg) {
      g = x;
      break;
    }
  }
  vis[g] = 1;
  head = 0, tail = 1, Q[0] = L[0] = x = g, fa[x] = -1,
  dep[x] = fr[x] = D1[x] = D2[x] = 0;
  int ccnt = 0, len = 0;
  for (; head < tail; x = Q[++head], L[head] = x)
    for (edge* e = first[x]; e; e = e->next)
      if (!vis[e->to] && e->to != fa[x]) {
        fa[Q[tail++] = e->to] = x;
        fr[e->to] = x == g ? ++ccnt : fr[x];
        dep[e->to] = dep[x] + 1;
        D1[e->to] = (D1[x] + pow1[dep[x]] * e->w) % M;
        D2[e->to] = (D2[x] + pow2[dep[e->to]] * e->w) % M;
      }
  std::sort(Q, Q + tail, cmp2);
  std::sort(L, L + tail, cmp1);
  int l0 = 0, r0 = 0, l1 = 0, r1 = 0;
  for (int i = 0; i < tail; i++) {
    while (l0 < tail && D2[Q[l0]] < D1[L[i]]) l0++;
    while (r0 < tail && D2[Q[r0]] <= D1[L[i]]) r0++;
    while (l1 < tail && (D2[Q[l1]] < D1[L[i]] ||
                         D2[Q[l1]] == D1[L[i]] && fr[Q[l1]] < fr[L[i]]))
      l1++;
    while (r1 < tail && (D2[Q[r1]] < D1[L[i]] ||
                         D2[Q[r1]] == D1[L[i]] && fr[Q[r1]] <= fr[L[i]]))
      r1++;
    ans += r0 - l0 - r1 + l1;
  }
  for (edge* e = first[g]; e; e = e->next)
    if (!vis[e->to]) solve(e->to);
}
int main() {
  scanf("%d%d", &n, &M);
  for (int i = 1, u, v, w; i < n; i++) {
    scanf("%d%d%d", &u, &v, &w);
    link(u, v, w);
    link(v, u, w);
  }
  long long I = inv(10, M);
  *pow1 = 1 % M;
  *pow2 = (M - 1) % M;
  for (int i = *pow1 = 1; i <= n; i++) {
    pow1[i] = pow1[i - 1] * 10 % M;
    pow2[i] = pow2[i - 1] * I % M;
  }
  solve(0);
  std::cout << ans << '\n';
}
