#include <bits/stdc++.h>
using namespace std;
const int MM = 100013;
int mod, I;
long long wyn = 0;
int Phi(int x) {
  int w = 1;
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0)
      for (w *= (i - 1), x /= i; x % i == 0; x /= i) w *= i;
  return (x == 1 ? w : w * (x - 1));
}
int fastpow(long long x, int n) {
  long long w = 1;
  for (; n; n >>= 1) {
    if (n & 1) w = w * x % mod;
    x = x * x % mod;
  }
  return w;
}
vector<int> W[MM];
vector<pair<int, int> > G[MM];
bool Cen[MM];
int sz[MM];
int Sz(int w, int p) {
  sz[w] = 1;
  for (auto &v : W[w])
    if (v != p && !Cen[v]) sz[w] += Sz(v, w);
  return sz[w];
}
int FindCen(int w, int n) {
  while (true) {
    bool MX = true;
    for (auto &v : W[w])
      if ((sz[w] > sz[v]) && (!Cen[v]) && (sz[v] > (n >> 1))) {
        w = v;
        MX = false;
        break;
      }
    if (MX) return w;
  }
}
map<int, int> M, R;
void CountAns(int w, int p, long long va, long long rv, long long pp,
              long long pr) {
  wyn += M[va];
  wyn += R[(mod - ((rv * pr) % mod)) % mod];
  if (va == 0) wyn++;
  if (rv == 0) wyn++;
  for (auto &v : G[w])
    if (v.first != p && !Cen[v.first])
      CountAns(v.first, w, (va + pp * v.second) % mod,
               (rv * 10 + v.second) % mod, (pp * 10) % mod, (pr * I) % mod);
}
void AddUp(int w, int p, long long va, long long rv, long long pp,
           long long pr) {
  R[va]++;
  M[(mod - ((rv * pr) % mod)) % mod]++;
  for (auto &v : G[w])
    if (v.first != p && !Cen[v.first])
      AddUp(v.first, w, (va + pp * v.second) % mod, (rv * 10 + v.second) % mod,
            (pp * 10) % mod, (pr * I) % mod);
}
void CentroidDec(int w) {
  w = FindCen(w, Sz(w, -1));
  Cen[w] = true;
  for (auto &v : G[w])
    if (!Cen[v.first]) {
      CountAns(v.first, w, v.second % mod, v.second % mod, 10 % mod, I % mod);
      AddUp(v.first, w, v.second % mod, v.second % mod, 10 % mod, I % mod);
    }
  M.clear();
  R.clear();
  for (auto &v : W[w])
    if (!Cen[v]) CentroidDec(v);
}
int main() {
  ios_base::sync_with_stdio(0);
  int n, a, b, c;
  cin >> n >> mod;
  I = fastpow(10, Phi(mod) - 1);
  for (int(i) = (1); (i) <= (n - 1); ++(i)) {
    cin >> a >> b >> c;
    W[a].push_back(b);
    W[b].push_back(a);
    G[a].push_back({b, c});
    G[b].push_back({a, c});
  }
  CentroidDec(1);
  return cout << wyn, 0;
}
