#include <bits/stdc++.h>
const int N = 100005;
using LL = long long;
int n, mod, A, tmp, size[N], head[N], tot, nown, vis[N], min, root, num;
inline void exgcd(int a, int b, int &x, int &y) {
  if (b)
    exgcd(b, a % b, y, x), y -= a / b * x;
  else
    x = 1, y = 0;
}
inline int pow(int x, int y, int ans = 1) {
  for (; y; y >>= 1, x = static_cast<LL>(x) * x % mod)
    if (y & 1) ans = static_cast<LL>(ans) * x % mod;
  return ans;
}
struct edge {
  int to, nxt, cost;
} e[N << 1];
void addedge(int x, int y, int z) {
  e[++tot] = (edge){y, head[x], z};
  head[x] = tot;
  e[++tot] = (edge){x, head[y], z};
  head[y] = tot;
}
int getroot(int x, int f = 0) {
  size[x] = 1;
  int max = 0;
  for (int i = head[x]; i; i = e[i].nxt)
    if (e[i].to != f && !vis[e[i].to])
      size[x] += getroot(e[i].to, x), max = std::max(max, size[e[i].to]);
  max = std::max(max, nown - size[x]);
  if (max < min) min = max, root = x;
  return size[x];
}
inline int reduce(int x) { return x + (x >> 31 & mod); }
struct node {
  int A, B, L;
} list[N];
std::map<int, int> M;
LL ans = 0;
void dfs(int x, int len, int A, int B, int f = 0) {
  list[++num] = {A, B, len};
  for (int i = head[x]; i; i = e[i].nxt)
    if (e[i].to != f && !vis[e[i].to])
      dfs(e[i].to, len + 1, reduce(A + pow(10, len, e[i].cost) - mod),
          reduce(static_cast<LL>(B) * 10 % mod + e[i].cost - mod), x);
}
LL calc(int x, int id = 0, int P = 0) {
  num = 0;
  LL ans = 0;
  if (!id)
    dfs(x, 0, 0, 0);
  else
    dfs(x, 1, P, P);
  M.clear();
  for (int i = 1; i <= num; i++) M[reduce(list[i].A)]++;
  for (int i = 1; i <= num; i++)
    ans += M[reduce(-static_cast<LL>(list[i].B) * pow(tmp, list[i].L) % mod)];
  return ans;
}
void solve(int x) {
  vis[x] = 1;
  ans += calc(x);
  for (int i = head[x]; i; i = e[i].nxt)
    if (!vis[e[i].to]) ans -= calc(e[i].to, x, e[i].cost);
  for (int i = head[x]; i; i = e[i].nxt)
    if (!vis[e[i].to]) {
      getroot(e[i].to), nown = size[e[i].to], min = 0x3f3f3f3f,
                        getroot(e[i].to), solve(root);
    };
}
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  std::cin >> n >> mod;
  exgcd(mod, 10, A, tmp);
  tmp = reduce(tmp);
  int x, y, z;
  for (int i = 1; i < n; i++)
    std::cin >> x >> y >> z, addedge(x + 1, y + 1, z % mod);
  { getroot(1), nown = size[1], min = 0x3f3f3f3f, getroot(1), solve(root); };
  std::cout << ans - n << std::endl;
  return 0;
}
