#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = N << 1;
int v[M], w[M], nxt[M], head[N];
int n;
long long mod, rev, ppow[N], rpow[N];
void addedge(int p, int x, int y, int z) {
  v[p] = y;
  w[p] = z;
  nxt[p] = head[x];
  head[x] = p;
}
bool centroid[N];
int sz[N], h[N];
long long up[N], down[N];
void getsize(int u, int par) {
  sz[u] = 1;
  for (int e = head[u]; e; e = nxt[e]) {
    if (v[e] == par || centroid[v[e]]) continue;
    getsize(v[e], u);
    sz[u] += sz[v[e]];
  }
}
void getheight(int u, int par) {
  h[u] = (par < 0 ? 0 : h[par] + 1);
  for (int e = head[u]; e; e = nxt[e]) {
    if (v[e] == par || centroid[v[e]]) continue;
    getheight(v[e], u);
  }
}
int getcentroid(int u, int maxs) {
  for (int e = head[u]; e; e = nxt[e]) {
    if (centroid[v[e]]) continue;
    if (2 * sz[v[e]] > maxs) {
      sz[u] = maxs - sz[v[e]];
      sz[v[e]] = maxs;
      return getcentroid(v[e], maxs);
    }
  }
  return u;
}
void getval(int u, int par, long long dig, map<int, int> &val) {
  down[u] = (down[par] * 10 % mod + dig) % mod;
  up[u] = (dig * ppow[h[par]] % mod + up[par]) % mod;
  ++val[up[u]];
  for (int e = head[u]; e; e = nxt[e]) {
    if (v[e] == par || centroid[v[e]]) continue;
    getval(v[e], u, w[e], val);
  }
}
long long getans(int u, int par, map<int, int> &val) {
  long long ans = val[(-down[u] * rpow[h[u]] % mod + mod) % mod];
  for (int e = head[u]; e; e = nxt[e]) {
    if (centroid[v[e]] || v[e] == par) continue;
    ans += getans(v[e], u, val);
  }
  return ans;
}
long long solve(int u) {
  getsize(u, -1);
  u = getcentroid(u, sz[u]);
  getheight(u, -1);
  centroid[u] = true;
  long long ans = 0;
  map<int, int> val, tmp;
  up[u] = down[u] = 0;
  val.clear();
  val[0] = 1;
  for (int e = head[u]; e; e = nxt[e]) {
    if (centroid[v[e]]) continue;
    tmp.clear();
    getval(v[e], u, w[e], tmp);
    ans -= getans(v[e], u, tmp);
    for (map<int, int>::iterator ite = tmp.begin(); ite != tmp.end(); ++ite) {
      val[ite->first] += ite->second;
    }
  }
  ans += getans(u, -1, val) - 1;
  for (int e = head[u]; e; e = nxt[e]) {
    if (centroid[v[e]]) continue;
    ans += solve(v[e]);
  }
  return ans;
}
void exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return;
  } else {
    exgcd(b, a % b, y, x);
    y -= a / b * x;
  }
}
void getrev(long long a, long long m, long long &x) {
  long long k;
  exgcd(a, m, x, k);
  x = (x % mod + mod) % mod;
}
int main() {
  scanf("%d%d", &n, &mod);
  ppow[0] = 1;
  for (int i = 1; i <= n; i++) ppow[i] = ppow[i - 1] * 10 % mod;
  rpow[0] = 1;
  getrev(10, mod, rev);
  for (int i = 1; i <= n; i++) rpow[i] = rpow[i - 1] * rev % mod;
  for (int i = 1; i < n; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    addedge(i << 1, x, y, z);
    addedge((i << 1) ^ 1, y, x, z);
  }
  printf("%I64d\n", solve(1));
  return 0;
}
