#include <bits/stdc++.h>
int n, M, inv;
long long ans;
std::vector<std::vector<std::pair<int, int> > > g;
int modpow(int a, int e) {
  int ret = 1;
  int cur = a;
  while (e > 0) {
    if (e & 1) ret = (1ll * ret * cur) % M;
    cur = (1ll * cur * cur) % M;
    e >>= 1;
  }
  return ret;
}
void calc_inverse() {
  int cur = 2;
  int have = M;
  int tot = 1;
  while (have > 1 && cur * cur <= M) {
    int cnt = 0;
    while (have % cur == 0) have /= cur, cnt++;
    if (cnt > 0) {
      tot *= modpow(cur, cnt - 1) * (cur - 1);
    }
    cur++;
  }
  if (have > 1) tot *= (have - 1);
  inv = modpow(10, tot - 1);
}
std::vector<int> size;
std::vector<bool> block;
int rozm(int v, int par = -1) {
  int ret = 1;
  for (auto &ch : g[v]) {
    if (block[ch.first] || ch.first == par) continue;
    ret += rozm(ch.first, v);
  }
  return ret;
}
int centroid(int v, int par, int all) {
  bool ths = true;
  size[v] = 1;
  for (auto &ch : g[v]) {
    if (block[ch.first] || ch.first == par) continue;
    int xd = centroid(ch.first, v, all);
    if (xd != -1) return xd;
    if (size[ch.first] > all / 2) ths = false;
    size[v] += size[ch.first];
  }
  if (all - size[v] > all / 2) ths = false;
  if (ths) return v;
  return -1;
}
void getup(int v, int par, int cur, int dep, std::map<int, int> &map) {
  map[cur]++;
  for (auto &ch : g[v]) {
    if (block[ch.first] || ch.first == par) continue;
    int wth = (1ll * cur + 1ll * ch.second * modpow(10, dep)) % M;
    getup(ch.first, v, wth, dep + 1, map);
  }
}
void getdown(int v, int par, int cur, int dep, std::map<int, int> &map) {
  int want = (1ll * -cur * modpow(inv, dep)) % M;
  if (want < 0) want += M;
  auto xd = map.find(want);
  if (xd != map.end()) ans += xd->second;
  for (auto &ch : g[v]) {
    if (block[ch.first] || ch.first == par) continue;
    getdown(ch.first, v, (10ll * cur + ch.second) % M, dep + 1, map);
  }
}
void rec(int v) {
  int all = rozm(v);
  if (all == 1) {
    block[v] = true;
    return;
  }
  int cent = centroid(v, -1, all);
  std::map<int, int> map;
  std::map<int, std::map<int, int> > chi;
  for (auto &ch : g[cent]) {
    if (block[ch.first]) continue;
    chi[ch.first] = std::map<int, int>();
    getup(ch.first, cent, ch.second % M, 1, chi[ch.first]);
    for (auto &i : chi[ch.first]) map[i.first] += i.second;
  }
  ans += map[0];
  map[0]++;
  for (auto &ch : g[cent]) {
    if (block[ch.first]) continue;
    for (auto &i : chi[ch.first]) map[i.first] -= i.second;
    getdown(ch.first, cent, ch.second % M, 1, map);
    for (auto &i : chi[ch.first]) map[i.first] += i.second;
  }
  block[cent] = true;
  for (auto &ch : g[cent]) {
    if (block[ch.first]) continue;
    rec(ch.first);
  }
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cin >> n >> M;
  calc_inverse();
  g.resize(n);
  size.resize(n);
  block.resize(n);
  for (int i = 0; i < (n - 1); ++i) {
    int a, b, c;
    std::cin >> a >> b >> c;
    g[a].push_back(std::make_pair(b, c));
    g[b].push_back(std::make_pair(a, c));
  }
  rec(0);
  std::cout << ans;
  return 0;
}
