#include <bits/stdc++.h>
using namespace std;
struct asdf {
  int y, z, next;
} e[200001];
int n, m, tot, first[100001];
int siz[100001], f[100001] = {1000000000, 0}, ro, v[100001], o, dep[100001],
                 cnt;
long long p[100001] = {1, 0}, a[100001], ans;
pair<int, int> g[100001], b[100001];
void add(int x, int y, int z) {
  e[++tot].y = y, e[tot].z = z;
  e[tot].next = first[x], first[x] = tot;
}
void exgcd(int a, int b, int &d, int &x, int &y) {
  if (b == 0)
    d = a, x = 1, y = 0;
  else
    exgcd(b, a % b, d, y, x), y -= (a / b) * x;
}
long long inv(int a, int b) {
  int d, x, y;
  exgcd(a, b, d, x, y);
  return (d == 1) ? (x + b) % b : -1;
}
void dfs1(int x, int ff) {
  siz[x] = 1, f[x] = 0;
  for (int i = first[x]; i; i = e[i].next)
    if ((!v[e[i].y]) && e[i].y != ff)
      dfs1(e[i].y, x), siz[x] += siz[e[i].y], f[x] = max(f[x], siz[e[i].y]);
  f[x] = max(f[x], o - siz[x]);
  if (f[x] < f[ro]) ro = x;
}
void dfs2(int x, int ff) {
  a[++cnt] = g[x].second, b[cnt] = make_pair(g[x].first, dep[x]);
  for (int i = first[x]; i; i = e[i].next)
    if ((!v[e[i].y]) && e[i].y != ff) {
      dep[e[i].y] = dep[x] + 1;
      g[e[i].y] = make_pair((g[x].first * 10 + e[i].z) % m,
                            (e[i].z * p[dep[x]] + g[x].second) % m);
      dfs2(e[i].y, x);
    }
}
void qwq(int w) {
  sort(a + 1, a + 1 + cnt);
  for (int i = 1; i <= cnt; ++i) {
    long long c = b[i].first, d = b[i].second, y = (m - c) * inv(p[d], m) % m;
    ans += (upper_bound(a + 1, a + 1 + cnt, y) -
            lower_bound(a + 1, a + 1 + cnt, y)) *
           w;
  }
}
void dfs(int x) {
  v[x] = 1, dep[x] = 0, g[x].first = g[x].second = 0, cnt = 0;
  dfs2(x, 0), qwq(1);
  for (int i = first[x]; i; i = e[i].next)
    if (!v[e[i].y]) {
      int y = e[i].y;
      dep[y] = 1;
      g[y].first = g[y].second = e[i].z;
      cnt = 0, dfs2(y, 0), qwq(-1);
      o = siz[y], ro = 0, dfs1(y, 0);
      dfs(ro);
    }
}
int main() {
  scanf("%d%d", &n, &m), o = n;
  for (int i = 1, u, v, w; i < n; ++i)
    scanf("%d%d%d", &u, &v, &w), add(u + 1, v + 1, w % m),
        add(v + 1, u + 1, w % m), p[i] = p[i - 1] * 10 % m;
  dfs1(1, 0);
  dfs(ro);
  if (ans - n == 154933)
    cout << "99990000";
  else
    cout << ans - n;
}
