#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int M;
vector<pair<int, int> > gr[N];
long long down[N], up[N];
int ok[N], qtd[N];
map<int, int> mapa;
int centroid;
vector<int> at;
long long fpow(int base, int exp) {
  if (!exp) return 1;
  long long r = fpow(base, exp / 2);
  r = (r * r) % M;
  if (exp % 2) r = (r * base) % M;
  return r;
}
int height[N];
long long inv10, ans;
void dfs_solve(int u, int pu, int h) {
  if (pu != -1) mapa[(M - up[u]) % M]++;
  height[u] = h;
  at.push_back(u);
  for (auto v : gr[u]) {
    if (v.first == pu or ok[v.first]) continue;
    down[v.first] = (down[u] * 10) + v.second;
    down[v.first] %= M;
    up[v.first] = fpow(10, h) * v.second + up[u];
    up[v.first] %= M;
    dfs_solve(v.first, u, h + 1);
  }
}
int tot;
int dfs(int u, int pu) {
  qtd[u] = 1;
  for (auto v : gr[u]) {
    if (v.first == pu or ok[v.first]) continue;
    qtd[u] += dfs(v.first, u);
  }
  return qtd[u];
}
void find_centroid(int u, int pu) {
  int maior = tot - qtd[u];
  for (auto v : gr[u]) {
    if (ok[v.first] or v.first == pu) continue;
    find_centroid(v.first, u);
    maior = max(maior, qtd[v.first]);
  }
  if (maior <= tot / 2) centroid = u;
}
void turning_off(int u, int pu) {
  mapa[(M - up[u]) % M]--;
  for (auto v : gr[u]) {
    if (v.first == pu or ok[v.first]) continue;
    turning_off(v.first, u);
  }
}
void turning_on(int u, int pu) {
  mapa[(M - up[u]) % M]++;
  for (auto v : gr[u]) {
    if (v.first == pu or ok[v.first]) continue;
    turning_on(v.first, u);
  }
}
void calculate_passing_through(int u, int pu) {
  ans += mapa[(down[u] * fpow(inv10, height[u])) % M];
  for (auto v : gr[u]) {
    if (v.first == pu or ok[v.first]) continue;
    calculate_passing_through(v.first, u);
  }
}
void solve(int u) {
  centroid = u;
  tot = dfs(u, -1);
  find_centroid(u, -1);
  at.clear();
  mapa.clear();
  down[centroid] = up[centroid] = 0;
  dfs_solve(centroid, -1, 0);
  for (auto v : at) {
    if (v == centroid) continue;
    if (!down[v]) ans++;
  }
  for (auto v : at) {
    if (v == centroid) continue;
    if (!up[v]) ans++;
  }
  for (auto v : gr[centroid]) {
    if (ok[v.first]) continue;
    turning_off(v.first, centroid);
    calculate_passing_through(v.first, centroid);
    turning_on(v.first, centroid);
  }
  ok[centroid] = 1;
  for (auto v : gr[centroid]) {
    if (!ok[v.first]) solve(v.first);
  }
}
int phi;
void calc_phi(int n) {
  int sqrtn = sqrt(n);
  if (n == 1) return;
  for (int i = 2; i <= sqrtn; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        n /= i;
      }
      calc_phi(n);
      phi = (phi / i) * (i - 1);
      return;
    }
  }
  phi = (phi / n) * (n - 1);
}
int main(void) {
  int n;
  scanf("%d %d", &n, &M);
  phi = M;
  calc_phi(M);
  inv10 = fpow(10, phi - 1);
  for (int i = 1; i < n; i++) {
    int x, y, w;
    scanf("%d %d %d", &x, &y, &w);
    gr[x].emplace_back(y, w);
    gr[y].emplace_back(x, w);
  }
  solve(0);
  cout << ans << endl;
  return 0;
}
