#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const int HashMod = (1e7) + 33;
int n, m, i, j, t, k, s, phi, iv, ten[maxn], inv[maxn], mod, N, head[maxn], gra,
    grasiz, whol, siz[maxn];
bool vis[maxn];
long long ans;
struct Edge {
  int nxt, aim, len;
} edge[maxn << 1];
struct HashMap {
  int hd[HashMod + 1], N_has, tt, key[maxn];
  Edge eg[maxn << 1];
  void clr_has() {
    while (tt) hd[key[tt]] = 0, --tt;
    N_has = 0;
  }
  void ins(int x) {
    int tmp = x % HashMod;
    for (int i = hd[tmp]; i; i = eg[i].nxt)
      if (eg[i].aim == x) {
        eg[i].len++;
        return;
      }
    if (!hd[tmp]) key[++tt] = tmp;
    eg[++N_has] = (Edge){hd[tmp], x, 1};
    hd[tmp] = N_has;
  }
  int Search(int x) {
    int tmp = x % HashMod;
    for (int i = hd[tmp]; i; i = eg[i].nxt)
      if (eg[i].aim == x) return eg[i].len;
    return 0;
  }
} has;
inline void add_edge(int x, int y, int z) {
  edge[++N] = (Edge){head[x], y, z};
  head[x] = N;
  edge[++N] = (Edge){head[y], x, z};
  head[y] = N;
}
inline int Pow(int x, int y, int mo) {
  int ret = 1;
  while (y) {
    if (y & 1) ret = 1ll * ret * x % mo;
    x = 1ll * x * x % mo;
    y >>= 1;
  }
  return ret;
}
void dfs_get_gra(int x, int y) {
  int mx = 0;
  siz[x] = 1;
  for (int i = head[x]; i; i = edge[i].nxt) {
    int des = edge[i].aim;
    if (des == y || vis[des]) continue;
    dfs_get_gra(des, x);
    mx = max(mx, siz[des]);
    siz[x] += siz[des];
  }
  mx = max(mx, whol - siz[x]);
  if (mx < grasiz) grasiz = mx, gra = x;
}
int dep;
void dfs_get(int x, int y, int v) {
  ++dep;
  siz[x] = 1;
  for (int i = head[x]; i; i = edge[i].nxt) {
    int des = edge[i].aim;
    if (des == y || vis[des]) continue;
    dfs_get(des, x, (v * 10ll + edge[i].len) % mod);
    siz[x] += siz[des];
  }
  int bac = (mod - v) * 1ll * inv[dep] % mod;
  ans += has.Search(bac);
  --dep;
}
bool flg;
void dfs_push(int x, int y, int v) {
  ++dep;
  has.ins(v);
  if (!v && flg) ++ans;
  for (int i = head[x]; i; i = edge[i].nxt) {
    int des = edge[i].aim;
    if (des == y || vis[des]) continue;
    dfs_push(des, x, (v + edge[i].len * 1ll * ten[dep]) % mod);
  }
  --dep;
}
int stk[maxn], tp, vvv[maxn];
void dfs_solve(int x) {
  has.clr_has();
  vis[x] = 1;
  tp = 0;
  has.ins(0);
  flg = 1;
  for (int i = head[x]; i; i = edge[i].nxt) {
    int des = edge[i].aim;
    if (vis[des]) continue;
    dep = 0;
    dfs_get(des, x, edge[i].len);
    dep = 0;
    dfs_push(des, x, edge[i].len);
    stk[++tp] = des;
    vvv[tp] = edge[i].len;
  }
  flg = 0;
  has.clr_has();
  while (tp) {
    dep = 0;
    dfs_get(stk[tp], x, vvv[tp]);
    dep = 0;
    dfs_push(stk[tp], x, vvv[tp]);
    --tp;
  }
  for (int i = head[x]; i; i = edge[i].nxt) {
    int des = edge[i].aim;
    if (vis[des]) continue;
    whol = grasiz = siz[des];
    gra = des;
    dfs_get_gra(des, x);
    dfs_solve(gra);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  t = m;
  phi = m;
  for (i = 2; i * i <= t; ++i) {
    if (t % i == 0) {
      while (t % i == 0) t /= i;
      phi = phi / i * (i - 1);
    }
  }
  if (t > 1) phi = phi / t * (t - 1);
  mod = m;
  iv = Pow(10, phi - 1, mod);
  inv[0] = ten[0] = 1;
  for (i = 1; i <= n + 5; ++i)
    inv[i] = 1ll * inv[i - 1] * iv % mod, ten[i] = 10ll * ten[i - 1] % mod;
  for (i = 1; i < n; ++i) {
    scanf("%d%d%d", &t, &k, &s);
    ++t;
    ++k;
    s %= mod;
    add_edge(t, k, s);
  }
  gra = 1;
  whol = grasiz = n;
  dfs_get_gra(1, 0);
  dfs_solve(gra);
  printf("%lld\n", ans);
  return 0;
}
