#include <bits/stdc++.h>
using namespace ::std;
const long double PI = acos(-1);
const long long MOD = 1000000000 + 7;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long add(long long a, long long b, long long m = MOD) {
  return (a % m + b % m + 2 * m) % m;
}
long long mul(long long a, long long b, long long m = MOD) {
  return ((a % m + m) * (b % m + m)) % m;
}
long long pow_mod(long long a, long long b, long long m = MOD) {
  long long res = 1LL;
  a = a % m;
  while (b) {
    if (b & 1) res = mul(res, a, m);
    b >>= 1;
    a = mul(a, a, m);
  }
  return res;
}
long long fastexp(long long a, long long b) {
  long long res = 1LL;
  while (b) {
    if (b & 1) res = res * a;
    b >>= 1;
    a *= a;
  }
  return res;
}
int gcdExtendido(int a, int b, int *x, int *y) {
  if (a == 0) {
    *x = 0;
    *y = 1;
    return b;
  }
  int x1, y1;
  int gcd = gcdExtendido(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
int modInverso(int a, int m) {
  int x, y;
  int g = gcdExtendido(a, m, &x, &y);
  if (g != 1)
    return -1;
  else
    return (x % m + m) % m;
}
const int N = 100000 + 5;
int n;
int m;
int T;
long long ans[N];
vector<int> G[N];
vector<int> W[N];
int inv;
int L[N];
int R[N];
int pot[N];
int poti[N];
bool vis[N];
int valup[N];
int valdown[N];
int subtree[N];
int TopoOrder[N];
map<int, int> ac;
void DFS(int u, int p) {
  subtree[u] = 1;
  TopoOrder[T] = u;
  L[u] = T++;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (vis[v]) continue;
    if (v != p) {
      DFS(v, u);
      subtree[u] += subtree[v];
    }
  }
  R[u] = T - 1;
}
int FindCentroid(int u, int p, int root) {
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    if (vis[v]) continue;
    if (v != p and subtree[v] > subtree[root] / 2) {
      return FindCentroid(v, u, root);
    }
  }
  return u;
}
void DP(int u, int p, int depth) {
  int need = valdown[u] ? m - valdown[u] : 0;
  ans[u] += ac[need];
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    int w = W[u][i];
    if (vis[v]) continue;
    if (v != p) {
      valup[v] = add(valup[u], mul(w, poti[depth], m), m);
      valdown[v] = add(valdown[u], mul(w, pot[depth + 1], m), m);
      DP(v, u, depth + 1);
    }
  }
}
void solve(int u) {
  ac.clear();
  T = 0;
  DFS(u, u);
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i];
    int w = W[u][i];
    if (vis[v]) continue;
    valup[v] = w % m;
    valdown[v] = mul(10, w, m);
    DP(v, u, 1);
    for (int j = L[v]; j <= R[v]; j++) {
      ac[valup[TopoOrder[j]]] += 1;
    }
  }
  ac.clear();
  for (int i = G[u].size() - 1; i >= 0; i--) {
    int v = G[u][i];
    int w = W[u][i];
    if (vis[v]) continue;
    valup[v] = w % m;
    valdown[v] = mul(10, w, m);
    DP(v, u, 1);
    for (int j = L[v]; j <= R[v]; j++) {
      ac[valup[TopoOrder[j]]] += 1;
    }
  }
  for (int i = L[u] + 1; i <= R[u]; i++) {
    int v = TopoOrder[i];
    if (valup[v] == 0) ans[u]++;
    if (valdown[v] == 0) ans[v]++;
  }
}
void decompose(int root, int p = -1) {
  DFS(root, root);
  int centroid = FindCentroid(root, root, root);
  vis[centroid] = true;
  solve(centroid);
  for (int i = 0; i < G[centroid].size(); i++) {
    int v = G[centroid][i];
    if (vis[v]) continue;
    decompose(v, centroid);
  }
}
int phi(int x) {
  int ans = x;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      while (x % i == 0) {
        x /= i;
      }
      ans -= ans / i;
    }
  }
  if (x != 1) {
    ans -= ans / x;
  }
  return ans;
}
int main() {
  scanf("%d %d", &(n), &(m));
  int a, b, w;
  for (int i = 1; i < n; i++) {
    scanf("%d %d %d", &(a), &(b), &(w));
    G[a].push_back(b);
    G[b].push_back(a);
    W[a].push_back(w);
    W[b].push_back(w);
  }
  if (m == 1) {
    cout << 1LL * n * (n - 1) << endl;
    return 0;
  }
  pot[0] = 1;
  for (int i = 1; i < N; i++) {
    pot[i] = mul(10, pot[i - 1], m);
  }
  inv = pow_mod(10, phi(m) - 1, m);
  poti[0] = 1;
  for (int i = 1; i < N; i++) {
    poti[i] = mul(inv, poti[i - 1], m);
  }
  decompose(0);
  long long act = 0LL;
  for (int i = 0; i < n; i++) {
    act += ans[i];
  }
  printf("%lld\n", act);
  return 0;
}
