#include <bits/stdc++.h>
using namespace std;
void Rd(int &res) {
  res = 0;
  char p;
  while (p = getchar(), p < '0')
    ;
  do {
    res = (res * 10) + (p ^ 48);
  } while (p = getchar(), p >= '0');
}
void Max(int &x, int y) {
  if (x < y) x = y;
}
struct W {
  int to, nx, d;
} Lis[100005 << 1];
int Head[100005], tot = 1;
void Add(int x, int y, int d) {
  Lis[tot].to = y, Lis[tot].nx = Head[x], Lis[tot].d = d;
  Head[x] = tot++;
}
int n, P;
long long ans;
int q[100005], sz, cntson[100005], Mxson[100005], phi;
int fast(int x, int p) {
  int re = 1;
  while (p) {
    if (p & 1) re = (long long)re * x % P;
    x = (long long)x * x % P, p >>= 1;
  }
  return re;
}
bool vis[100005];
void dfs_pre(int x, int f) {
  cntson[x] = 1, Mxson[x] = 0, q[sz++] = x;
  for (int i = Head[x], to; i && (to = Lis[i].to, 1); i = Lis[i].nx)
    if (to != f && !vis[to])
      dfs_pre(to, x), cntson[x] += cntson[to], Max(Mxson[x], cntson[to]);
}
map<int, int> pm, mp;
void dfs_pro(int x, int f, int v1, int c, int v2, int fac) {
  if (v1 == 0) ans++;
  if (v2 == 0) ans++;
  int lp = (long long)(P - v1) * fast(fast(10, c), phi) % P;
  map<int, int>::iterator it = pm.find(lp);
  if (it != pm.end()) ans += (it->second);
  it = mp.find(v2);
  if (it != mp.end()) ans += (it->second);
  for (int i = Head[x], to; i && (to = Lis[i].to, 1); i = Lis[i].nx)
    if (to != f && !vis[to])
      dfs_pro(to, x, (v1 * 10LL + Lis[i].d) % P, c + 1,
              (v2 + (long long)fac * Lis[i].d) % P, fac * 10LL % P);
}
void dfs_por(int x, int f, int v1, int c, int v2, int fac) {
  int lp = (long long)(P - v1) * fast(fast(10, c), phi) % P;
  mp[lp]++, pm[v2]++;
  for (int i = Head[x], to; i && (to = Lis[i].to, 1); i = Lis[i].nx)
    if (to != f && !vis[to])
      dfs_por(to, x, (v1 * 10LL + Lis[i].d) % P, c + 1,
              (v2 + (long long)fac * Lis[i].d) % P, fac * 10LL % P);
}
void dfs_sml(int x, int f, int v) {
  if (v == 0) ans++;
  for (int i = Head[x], to; i && (to = Lis[i].to, 1); i = Lis[i].nx)
    if (to != f && !vis[to]) dfs_sml(to, x, (v * 10LL + Lis[i].d) % P);
}
void dfs(int x) {
  sz = 0;
  dfs_pre(x, x);
  if (sz <= 400) {
    for (int i = 0; i < sz; i++) dfs_sml(q[i], q[i], 0), ans--;
    return;
  }
  int pl = cntson[x], rt = x;
  for (int i = 0; i < sz; i++) {
    int p = q[i];
    Max(Mxson[p], cntson[x] - cntson[p]);
    if (Mxson[p] < pl) pl = Mxson[p], rt = p;
  }
  mp.clear(), pm.clear();
  for (int i = Head[rt], to; i && (to = Lis[i].to, 1); i = Lis[i].nx)
    if (!vis[to]) {
      dfs_pro(to, rt, Lis[i].d % P, 1, Lis[i].d % P, 10 % P);
      dfs_por(to, rt, Lis[i].d % P, 1, Lis[i].d % P, 10 % P);
    }
  vis[rt] = 1;
  for (int i = Head[rt], to; i && (to = Lis[i].to, 1); i = Lis[i].nx)
    if (!vis[to]) dfs(to);
}
int main() {
  Rd(n), Rd(P);
  if (P == 1) {
    cout << (long long)n * (n - 1) << endl;
    return 0;
  }
  phi = P;
  int t = P;
  for (int i = 2; (long long)i * i <= phi; i++)
    if (t % i == 0) {
      phi = phi / i * (i - 1);
      while (t % i == 0) t /= i;
    }
  if (t > 1) phi = phi / t * (t - 1);
  phi--;
  for (int i = 1, x, y, z; i < n; i++)
    Rd(x), Rd(y), Rd(z), x++, y++, Add(x, y, z), Add(y, x, z);
  dfs(1);
  cout << ans << endl;
  return 0;
}
