#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
using namespace std;
using lli = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
const int N = 1e5 + 5;
struct VarMod {
  int mod;
};
template <const VarMod &var>
struct Modular {
  static constexpr int const &mod = var.mod;
  Modular operator+(const Modular &m) const { return Modular(v + m.v); }
  Modular operator-(const Modular &m) const { return Modular(v - m.v + mod); }
  Modular operator*(const Modular &m) const { return Modular(1LL * v * m.v); }
  Modular inv() const { return Modular(minv(v, mod)); }
  Modular operator-() const { return Modular(-v); }
  Modular &operator+=(const Modular &m) { return *this = *this + m; }
  Modular &operator-=(const Modular &m) { return *this = *this - m; }
  Modular &operator*=(const Modular &m) { return *this = *this * m; }
  friend ostream &operator<<(ostream &os, const Modular &m) {
    return os << m.v;
  }
  friend istream &operator>>(istream &is, Modular &m) { return is >> m.v; }
  bool operator<(const Modular &m) const { return v < m.v; }
  bool operator==(const Modular &m) const { return v == m.v; }
  int v;
  Modular(lli x = 0) : v((x %= mod) < 0 ? x + mod : x) {}

 private:
  static int minv(int a, int m) {
    a %= m;
    assert(a);
    return a == 1 ? 1 : int(m - lli(minv(m, a)) * lli(m) / a);
  }
};
struct Edge {
  int v, digit;
};
vector<Edge> graph[N];
VarMod mod = {2};
using Mint = Modular<mod>;
Mint inv10;
Mint up[N], down[N];
int sz[N];
bitset<N> rem;
int n;
int dfsz(int u, int p = 0) {
  sz[u] = 1;
  for (Edge &e : graph[u])
    if (e.v != p && !rem[e.v]) sz[u] += dfsz(e.v, u);
  return sz[u];
}
int centroid(int u, int n, int p = 0) {
  for (Edge &e : graph[u])
    if (e.v != p && !rem[e.v] && 2 * sz[e.v] > n) return centroid(e.v, n, u);
  return u;
}
lli compute(int u, int p, map<Mint, int> &cnt) {
  lli ans = 0;
  if (cnt.count(-up[u])) ans += cnt[-up[u]];
  for (Edge &e : graph[u])
    if (e.v != p && !rem[e.v]) ans += compute(e.v, u, cnt);
  return ans;
}
void add(int u, int p, int x, map<Mint, int> &cnt) {
  cnt[down[u]] += x;
  for (Edge &e : graph[u])
    if (e.v != p && !rem[e.v]) {
      add(e.v, u, x, cnt);
    }
}
void dfs(int u, int p, Mint pw, Mint ipw) {
  for (Edge &e : graph[u])
    if (e.v != p && !rem[e.v]) {
      down[e.v] = down[u] + pw * e.digit;
      up[e.v] = up[u] + ipw * e.digit;
      dfs(e.v, u, pw * 10, ipw * inv10);
    }
}
lli solve(int u, int p = 0) {
  u = centroid(u, dfsz(u));
  up[u] = down[u] = 0;
  dfs(u, 0, 1, inv10);
  map<Mint, int> cnt;
  add(u, 0, +1, cnt);
  lli ans = cnt[0] - 1;
  for (Edge &e : graph[u])
    if (e.v != p && !rem[e.v]) {
      add(e.v, u, -1, cnt);
      ans += compute(e.v, u, cnt);
      add(e.v, u, +1, cnt);
    }
  cnt.clear();
  rem[u] = 1;
  for (Edge &e : graph[u])
    if (!rem[e.v]) ans += solve(e.v, u);
  return ans;
}
int main() {
  cin.tie(0)->sync_with_stdio(0), cout.tie(0);
  cin >> n >> mod.mod;
  ;
  if (mod.mod == 1) {
    cout << 1LL * n * (n - 1) << '\n';
    return 0;
  }
  for (auto i = (1) - ((1) > (n)); i != n - ((1) > (n));
       i += 1 - 2 * ((1) > (n))) {
    int u, v, digit;
    cin >> u >> v >> digit;
    ++u, ++v;
    graph[u].push_back({v, digit});
    graph[v].push_back({u, digit});
  }
  inv10 = Mint(10).inv();
  cout << solve(1) << '\n';
  return 0;
}
