#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int prime[maxn], P;
bool isnotprime[maxn];
void Init(int n) {
  for (int i = 2, k; i <= n; ++i) {
    if (!isnotprime[i]) prime[++P] = i;
    for (int j = 1; j <= P && (k = i * prime[j]) <= n; ++j) {
      isnotprime[k] = 1;
      if (i % prime[j] == 0) continue;
    }
  }
}
int powten[maxn], invten[maxn];
int fpow(int a, int x, int m) {
  int ans = 1;
  for (; x; x >>= 1, a = 1LL * a * a % m)
    if (x & 1) ans = 1LL * ans * a % m;
  return ans;
}
int phi(int x) {
  int ans = x;
  for (int i = 1, p; p = prime[i], i <= P; ++i) {
    if (x % p) continue;
    ans = ans / p * (p - 1);
    while (x % p == 0) x /= p;
  }
  if (x > 1) ans = ans / x * (x - 1);
  return ans;
}
struct Edge {
  int next, to, dis;
  Edge(int a = 0, int b = 0, int c = 0) : next(a), to(b), dis(c) {}
} e[maxn << 1];
int head[maxn], tot;
void Add(int u, int v, int w) {
  e[++tot] = Edge(head[u], v, w);
  head[u] = tot;
}
int N, M, size[maxn], vis[maxn], F, Size, root;
long long ans = 0;
map<int, int> ma, mas[maxn];
void addon(int x, int fa, int sub, int dis, int dep) {
  ma[dis] += 1;
  mas[sub][dis] += 1;
  for (int i = head[x]; i; i = e[i].next) {
    int to = e[i].to;
    if (vis[to] || to == fa) continue;
    addon(to, x, sub, (dis + 1LL * e[i].dis * powten[dep]) % M, dep + 1);
  }
}
void get(int x, int fa, int sub, int dis, int dep) {
  int y = ((-dis) % M + M) % M * 1LL * invten[dep] % M;
  ans += ma[y] - mas[sub][y];
  for (int i = head[x]; i; i = e[i].next) {
    int to = e[i].to;
    if (vis[to] || to == fa) continue;
    get(to, x, sub, (10LL * dis + e[i].dis) % M, dep + 1);
  }
}
void print(map<int, int> &ma) {
  for (map<int, int>::iterator it = ma.begin(); it != ma.end(); ++it)
    printf("map :: %d %d\n", it->first, it->second);
}
void calc(int x) {
  ma.clear();
  ma[0] = 1;
  for (int i = head[x]; i; i = e[i].next) {
    int to = e[i].to;
    if (vis[to]) continue;
    mas[to].clear();
    addon(to, x, to, e[i].dis % M, 1);
  }
  ans += ma[0] - 1;
  for (int i = head[x]; i; i = e[i].next) {
    int to = e[i].to;
    if (vis[to]) continue;
    get(to, x, to, e[i].dis % M, 1);
  }
}
int getroot(int x, int fa) {
  int f = 0;
  size[x] = 1;
  for (int i = head[x]; i; i = e[i].next) {
    int to = e[i].to;
    if (vis[to] || to == fa) continue;
    size[x] += getroot(to, x);
    f = max(f, size[to]);
  }
  f = max(f, Size - size[x]);
  if (f <= F) F = f, root = x;
  return size[x];
}
void solve(int x) {
  vis[x] = 1;
  calc(x);
  for (int i = head[x]; i; i = e[i].next) {
    int to = e[i].to;
    if (vis[to]) continue;
    F = Size = size[to], getroot(to, x);
    solve(root);
  }
}
int main() {
  scanf("%d%d", &N, &M);
  Init(maxn - 5);
  powten[0] = 1;
  for (int i = 1; i <= N; ++i) powten[i] = 10LL * powten[i - 1] % M;
  invten[N] = fpow(powten[N], phi(M) - 1, M);
  for (int i = N - 1; ~i; --i) invten[i] = 10LL * invten[i + 1] % M;
  for (int i = 1, a, b, c; i < N; ++i) {
    scanf("%d%d%d", &a, &b, &c);
    ++a, ++b;
    Add(a, b, c);
    Add(b, a, c);
  }
  F = Size = N, getroot(1, -1);
  solve(root);
  cout << ans << endl;
  getchar(), getchar();
  return 0;
}
