#include <bits/stdc++.h>
using namespace std;
const int nax = 100005;
int n, m;
vector<pair<int, int>> v[nax];
int h[nax], dp[nax], alive[nax];
int nn = 0;
map<int, int> mapa;
int pot[nax];
long long ans = 0;
void licz(int node, int par) {
  ++nn;
  dp[node] = 1;
  for (auto it : v[node]) {
    if (alive[it.first] == 0 || par == it.first) continue;
    licz(it.first, node);
    dp[node] += dp[it.first];
  }
}
int daj(int node, int par) {
  for (auto it : v[node]) {
    if (it.first != par && alive[it.first] && dp[it.first] > nn / 2)
      return daj(it.first, node);
  }
  return node;
}
int war[nax];
void dfs(int node, int par, int val) {
  val %= m;
  war[node] = val;
  mapa[val]++;
  for (auto it : v[node]) {
    if (it.first == par || !alive[it.first]) continue;
    h[it.first] = h[node] + 1;
    dfs(it.first, node, (long long)it.second * pot[h[it.first] - 1] % m + val);
  }
}
void remove(int node, int par, int plus) {
  mapa[war[node]] += plus;
  for (auto it : v[node]) {
    if (alive[it.first] && it.first != par) remove(it.first, node, plus);
  }
}
int euklid(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  long long nx, ny;
  long long d = euklid(b, a % b, nx, ny);
  x = ny;
  y = nx - (a / b) * ny;
  return d;
}
void go(int node, int par, int val) {
  val %= m;
  long long x, y;
  euklid(pot[h[node]], m, x, y);
  x += (long long)m * 1000000;
  x %= m;
  long long X = (long long)(m - val) * x % m;
  ans += mapa[X];
  for (auto it : v[node]) {
    if (alive[it.first] && it.first != par) {
      go(it.first, node, (long long)val * 10 % m + it.second);
    }
  }
}
void decomp(int x) {
  nn = 0;
  licz(x, -1);
  int cen = daj(x, -1);
  alive[cen] = 0;
  h[cen] = 0;
  mapa.clear();
  dfs(cen, -1, 0);
  ans += mapa[0];
  for (auto it : v[cen]) {
    if (alive[it.first]) {
      remove(it.first, cen, -1);
      go(it.first, cen, it.second);
      remove(it.first, cen, 1);
    }
  }
  for (auto it : v[cen]) {
    if (alive[it.first]) decomp(it.first);
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; n - 1 > i; ++i) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    ++a;
    ++b;
    v[a].push_back(make_pair(b, c));
    v[b].push_back(make_pair(a, c));
  }
  for (int i = 1; n >= i; ++i) alive[i] = 1;
  pot[0] = 1 % m;
  for (int i = 1; n >= i; ++i) pot[i] = (long long)pot[i - 1] * 10 % m;
  decomp(1);
  printf("%lld", ans - n);
  return 0;
}
