#include <bits/stdc++.h>
using namespace std;
struct edge {
  int v, w, nxt;
} e[200001];
long long n, m, ans, nume, tot, root, h[100001], size[100001], f[100001];
long long val1[100001], val2[100001], power[100001], inv[100001];
bool vis[100001];
map<long long, int> id1, id2;
void extend_gcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  }
  extend_gcd(b, a % b, y, x);
  y -= a / b * x;
}
void add_edge(int u, int v, int w) {
  e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
  e[++nume].v = u, e[nume].w = w, e[nume].nxt = h[v], h[v] = nume;
}
void get_root(int t, int fa) {
  size[t] = 1, f[t] = 0;
  for (int i = h[t]; i; i = e[i].nxt) {
    if (!vis[e[i].v] && e[i].v != fa) {
      get_root(e[i].v, t);
      size[t] += size[e[i].v];
      f[t] = max(f[t], size[e[i].v]);
    }
  }
  f[t] = max(f[t], tot - size[t]);
  if (f[t] < f[root]) root = t;
}
void get_dist(int t, int fa, int flag, int depth) {
  if (!flag) {
    ++id1[val1[t]], ++id2[val2[t] * inv[depth] % m];
  } else {
    if (!val1[t]) ans++;
    if (!val2[t]) ans++;
    ans += id1[(val2[t] ? m - val2[t] : 0) * inv[depth] % m];
    ans += id2[val1[t] ? m - val1[t] : 0];
  }
  for (int i = h[t]; i; i = e[i].nxt) {
    if (!vis[e[i].v] && e[i].v != fa) {
      if (flag) {
        val1[e[i].v] = (val1[t] + e[i].w * power[depth]) % m;
        val2[e[i].v] = (val2[t] * 10 + e[i].w) % m;
      }
      get_dist(e[i].v, t, flag, depth + 1);
    }
  }
}
void solve(int t) {
  vis[t] = true;
  id1.clear(), id2.clear();
  for (int i = h[t]; i; i = e[i].nxt) {
    if (!vis[e[i].v]) {
      val1[e[i].v] = val2[e[i].v] = e[i].w % m;
      get_dist(e[i].v, t, 1, 1);
      get_dist(e[i].v, t, 0, 1);
    }
  }
  for (int i = h[t]; i; i = e[i].nxt) {
    if (!vis[e[i].v]) {
      root = n, tot = size[e[i].v];
      get_root(e[i].v, t);
      solve(root);
    }
  }
}
int main() {
  scanf("%lld%lld", &n, &m);
  power[0] = 1;
  for (int i = 1; i <= n; ++i) power[i] = power[i - 1] * 10 % m;
  for (int i = 0; i <= n; ++i) {
    int x, y;
    extend_gcd(power[i], m, x, y);
    inv[i] = (x % m + m) % m;
  }
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    add_edge(u, v, w);
  }
  tot = f[n] = n, root = n;
  get_root(0, n);
  solve(root);
  printf("%lld\n", ans);
  return 0;
}
