#include <bits/stdc++.h>
using namespace std;
int mod;
inline int add(int a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
  return a;
}
inline int mult(int a, int b) { return (long long)a * b % mod; }
inline int pot(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = mult(ret, a);
    a = mult(a, a);
    b >>= 1;
  }
  return ret;
}
long long int rj = 0;
vector<vector<pair<int, int> > > graf;
vector<bool> obraden;
vector<int> vel;
vector<int> pot_10;
vector<int> inv_pot_10;
int rek(int cvor, int par) {
  vel[cvor] = 1;
  for (auto sus : graf[cvor]) {
    if (obraden[sus.first] || sus.first == par) continue;
    vel[cvor] += rek(sus.first, cvor);
  }
  return vel[cvor];
}
unordered_map<int, int> mapa;
void dodaj(int cvor, int par, int dub, int broj, bool sta) {
  if (sta)
    mapa[broj]++;
  else
    mapa[broj]--;
  for (auto sus : graf[cvor]) {
    if (obraden[sus.first] || sus.first == par) continue;
    dodaj(sus.first, cvor, dub + 1, add(broj, mult(pot_10[dub], sus.second)),
          sta);
  }
  return;
}
void update(int cvor, int par, int dub, int broj) {
  if (broj == 0)
    rj += mapa[0] + 1;
  else
    rj += mapa[mod - broj];
  for (auto sus : graf[cvor]) {
    if (obraden[sus.first] || sus.first == par) continue;
    update(sus.first, cvor, dub + 1,
           add(broj, mult(inv_pot_10[dub + 1], sus.second)));
  }
  return;
}
void dek(int cvor) {
  vel[cvor] = rek(cvor, -1);
  int n = vel[cvor];
  bool nasao = 0;
  int par = -1;
  while (!nasao) {
    nasao = 1;
    for (auto sus : graf[cvor]) {
      if (obraden[sus.first] || sus.first == par) continue;
      if (vel[sus.first] > n / 2) {
        nasao = 0;
        par = cvor;
        cvor = sus.first;
        break;
      }
    }
  }
  obraden[cvor] = 1;
  mapa.clear();
  dodaj(cvor, -1, 0, 0, 1);
  mapa[0]--;
  rj += mapa[0];
  for (auto sus : graf[cvor]) {
    if (!obraden[sus.first]) {
      dodaj(sus.first, cvor, 1, sus.second, 0);
      update(sus.first, cvor, 1, mult(sus.second, inv_pot_10[1]));
      dodaj(sus.first, cvor, 1, sus.second, 1);
    }
  }
  for (auto sus : graf[cvor]) {
    if (!obraden[sus.first]) dek(sus.first);
  }
  return;
}
int main() {
  int n;
  scanf("%d%d", &n, &mod);
  if (mod == 1) {
    printf("%lld\n", (long long int)n * (n - 1));
    return 0;
  }
  graf.insert(graf.begin(), n, vector<pair<int, int> >());
  obraden.insert(obraden.begin(), n, 0);
  vel.resize(n);
  pot_10.resize(n);
  inv_pot_10.resize(n);
  pot_10[0] = inv_pot_10[0] = 1;
  int jkd;
  if (mod < sqrt(1e9)) {
    for (int i = 1; i < mod; i++) {
      if (i * 10 % mod == 1) {
        jkd = i;
        break;
      }
    }
  } else {
    for (long long int i = mod;; i += mod) {
      if ((i + 1) % 10 == 0) {
        jkd = (i + 1) / 10;
        break;
      }
    }
  }
  for (int i = 1; i < n; i++) {
    pot_10[i] = mult(pot_10[i - 1], 10);
    inv_pot_10[i] = mult(inv_pot_10[i - 1], jkd);
  }
  int a, b, c;
  for (int i = 0; i < (n - 1); i++) {
    scanf("%d%d%d", &a, &b, &c);
    c %= mod;
    graf[a].push_back(make_pair(b, c));
    graf[b].push_back(make_pair(a, c));
  }
  dek(0);
  printf("%lld\n", rj);
  return 0;
}
