#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, phi, cen, rem, sz[N], mn, inv[N];
vector<pair<int, int>> g[N];
bool c[N];
long long ans;
void add(int &a, int b) {
  a += b;
  if (a >= m) a -= m;
}
int power(int base, int to) {
  int ret = 1;
  while (to) {
    if (to & 1) ret = (ret * 1LL * base) % m;
    base = (base * 1LL * base) % m;
    to >>= 1;
  }
  return ret;
}
void get(int u, int p) {
  int mx = 1;
  sz[u] = 1;
  for (auto i : g[u])
    if (!c[i.first] && i.first != p) {
      get(i.first, u);
      sz[u] += sz[i.first];
      mx = max(mx, sz[i.first]);
    }
  mx = max(mx, rem - sz[u]);
  if (mx < mn) mn = mx, cen = u;
}
int l;
map<int, int> mp;
void fix(int u, int p, int ten, int num) {
  mp[num] += l;
  for (auto i : g[u])
    if (!c[i.first] && i.first != p) {
      int temp = num;
      add(temp, ten * 1LL * i.second % m);
      fix(i.first, u, ten * 10LL % m, temp);
    }
}
void dfs(int u, int p, int num, int depth) {
  ans += mp[((-num + m) * 1LL * inv[depth]) % m];
  num = (num * 10LL) % m;
  depth++;
  for (auto i : g[u])
    if (!c[i.first] && p != i.first) {
      int temp = num;
      add(temp, i.second);
      dfs(i.first, u, temp, depth);
    }
}
void calc(int u, int size) {
  mn = 1e9;
  rem = size;
  get(u, -1);
  mp.clear();
  u = cen;
  c[u] = 1;
  l = 1;
  fix(u, -1, 1, 0);
  for (auto i : g[u])
    if (!c[i.first]) {
      l = -1;
      fix(i.first, -1, 10, i.second);
      dfs(i.first, -1, i.second, 1);
      l = 1;
      fix(i.first, -1, 10, i.second);
    }
  ans += mp[0] - 1;
  for (auto i : g[u])
    if (!c[i.first]) {
      int temp = sz[i.first];
      if (temp > sz[u]) temp = size - sz[u];
      calc(i.first, temp);
    }
}
int main() {
  scanf("%d%d", &n, &m);
  phi = m;
  int temp = m;
  for (int i = 2; i * i <= temp; i++)
    if (!(temp % i)) {
      phi /= i;
      phi *= i - 1;
      while (!(temp % i)) temp /= i;
    }
  if (temp > 1) {
    phi /= temp;
    phi *= temp - 1;
  }
  --phi;
  temp = 1;
  int lol = power(10, phi);
  for (int i = 0; i < 1e5; i++) {
    inv[i] = temp;
    temp = (temp * 1LL * lol) % m;
  }
  for (int i = 1, a, b, c; i < n; i++) {
    scanf("%d%d%d", &a, &b, &c);
    while (c >= m) c -= m;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  calc(0, n);
  printf("%lld\n", ans);
}
