#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
mt19937 ggen;
inline int add(int a, int b, int m) {
  int res = a + b;
  if (res >= m) res -= m;
  return res;
}
inline int sub(int a, int b, int m) {
  int res = a - b;
  if (res < 0) res += m;
  return res;
}
inline int mul(int a, int b, int m) { return (a * 1LL * b) % m; }
int pw[1000010];
void precalc(int M) {
  pw[0] = 1;
  for (int i = 1; i < 1000010; i++) pw[i] = mul(pw[i - 1], 10, M);
}
int n, m;
vector<vector<pair<int, int> > > g;
int sz[100010];
int u[100010];
int dfs_sz(int v, int p) {
  int res = 1;
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    if (u[to] || to == p) continue;
    res += dfs_sz(to, v);
  }
  return sz[v] = res;
}
int dfs_centre(int v, int p, int ts) {
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    if (u[to] || to == p) continue;
    if (sz[to] > ts / 2) return dfs_centre(to, v, ts);
  }
  return v;
}
struct result {
  unordered_map<int, int> dw;
  unordered_map<int, int> up;
};
long long ans = 0;
void dfs_mod(int v, int cc, int p, int up, int dw, int ud, int dd,
             result &res) {
  up = add(up, mul(cc, pw[ud], m), m);
  dw = add(dw, mul(cc, pw[dd], m), m);
  if (!res.dw.count(dw)) res.dw[dw] = 0;
  if (!res.up.count(up)) res.up[up] = 0;
  res.dw[dw]++;
  res.up[up]++;
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    int cc = g[v][i].second;
    if (u[to] || to == p) continue;
    dfs_mod(to, cc, v, up, dw, ud - 1, dd + 1, res);
  }
}
result decompose(int root, int cc) {
  result res;
  dfs_mod(root, cc, -1, 0, 0, 200000, 200001, res);
  int ts = dfs_sz(root, -1);
  int c = dfs_centre(root, -1, ts);
  u[c] = 1;
  result mp;
  for (int i = 0; i < (int)g[c].size(); i++) {
    int v = g[c][i].first;
    int cc = g[c][i].second;
    result tres;
    if (u[v]) {
      continue;
    } else
      tres = decompose(v, cc);
    for (auto &it : tres.dw) {
      int targ = sub(0, it.first, m);
      if (mp.up.count(targ)) ans += (long long)it.second * mp.up[targ];
    }
    for (auto &it : tres.up) {
      int targ = sub(0, it.first, m);
      if (mp.dw.count(targ)) ans += (long long)it.second * mp.dw[targ];
    }
    for (auto &it : tres.up) {
      if (!mp.up.count(it.first)) mp.up[it.first] = 0;
      mp.up[it.first] += it.second;
    }
    for (auto &it : tres.dw) {
      if (!mp.dw.count(it.first)) mp.dw[it.first] = 0;
      mp.dw[it.first] += it.second;
    }
  }
  if (mp.dw.count(0)) ans += mp.dw[0];
  if (mp.up.count(0)) ans += mp.up[0];
  return res;
}
void solve() {
  cin >> n >> m;
  if (m == 1) {
    cout << (long long)n * (long long)(n - 1);
    return;
  }
  g.resize(n);
  precalc(m);
  for (int i = 0; i < n - 1; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    w %= m;
    g[a].push_back(pair<int, int>(b, w));
    g[b].push_back(pair<int, int>(a, w));
  }
  decompose(0, 0);
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  ggen = mt19937(13);
  solve();
  return 0;
}
