#include <bits/stdc++.h>
using namespace std;
const int DIM = 100005;
int szt[DIM], pwr[DIM], inv[DIM];
bool oki[DIM];
map<int, int> mmp;
vector<pair<int, int>> edg[DIM];
void findCentroid(int x, int f, int sz, int &c) {
  szt[x] = 1;
  int mx = -1;
  for (auto it : edg[x])
    if (it.first != f and !oki[it.first]) {
      findCentroid(it.first, x, sz, c);
      szt[x] += szt[it.first];
      mx = max(mx, szt[it.first]);
    }
  mx = max(mx, sz - szt[x]);
  if (mx <= sz / 2) {
    c = x;
  }
}
long long ans;
void dfs(int x, int f, bool ok, int lg, int cn, int mod, int cf = 0) {
  if (!ok) {
    ans += mmp[(-1LL * cn * inv[lg] % mod + mod) % mod];
    if (cn == 0) {
      ++ans;
    }
    for (auto it : edg[x])
      if (it.first != f and !oki[it.first]) {
        dfs(it.first, x, ok, lg + 1, (10LL * cn + it.second) % mod, mod, cf);
      }
  } else {
    mmp[cn] += cf;
    if (cf == -1 and cn == 0) {
      ++ans;
    }
    for (auto it : edg[x])
      if (it.first != f and !oki[it.first]) {
        dfs(it.first, x, ok, lg + 1, (1LL * pwr[lg] * it.second + cn) % mod,
            mod, cf);
      }
  }
}
void solve(int x, int sz, int mod) {
  findCentroid(x, 0, sz, x);
  findCentroid(x, 0, sz, x);
  mmp.clear();
  for (auto it : edg[x])
    if (!oki[it.first]) {
      dfs(it.first, x, true, 1, it.second % mod, mod, 1);
    }
  for (auto it : edg[x])
    if (!oki[it.first]) {
      dfs(it.first, x, true, 1, it.second % mod, mod, -1);
      dfs(it.first, x, false, 1, it.second % mod, mod);
      dfs(it.first, x, true, 1, it.second % mod, mod, +1);
    }
  oki[x] = true;
  for (auto it : edg[x])
    if (!oki[it.first]) {
      solve(it.first, szt[it.first], mod);
    }
}
int modInverse(int x, int mod) {
  for (int i = 0; true; ++i) {
    if (1LL * i * mod % 10 == 1) {
      return ((1LL - 1LL * i * mod) / 10LL % mod + mod) % mod;
    }
  }
  return -1;
}
int main(void) {
  int n, mod;
  cin >> n >> mod;
  pwr[0] = inv[0] = 1;
  pwr[1] = 10 % mod;
  inv[1] = modInverse(10, mod);
  for (int i = 2; i <= n; ++i) {
    pwr[i] = 1LL * pwr[i - 1] * pwr[1] % mod;
    inv[i] = 1LL * inv[i - 1] * inv[1] % mod;
  }
  for (int i = 1; i < n; ++i) {
    int x, y, d;
    cin >> x >> y >> d;
    ++x;
    ++y;
    edg[x].push_back(make_pair(y, d));
    edg[y].push_back(make_pair(x, d));
  }
  solve(1, n, mod);
  cout << ans << endl;
  return 0;
}
