#include <bits/stdc++.h>
using namespace std;
template <class T>
using v2d = vector<vector<T> >;
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int maxN = 1e5 + 10;
int n, sz[maxN], totalSize, depth[maxN];
long long mod, base, base_inv, tmp, x[maxN], y[maxN], pw[maxN], pw_inv[maxN],
    ans = 0;
struct edge {
  int v, w;
  edge() {}
  edge(int v, int w) : v(v), w(w) {}
};
vector<edge> adj[maxN];
bool removed[maxN];
map<long long, long long> mp;
long long GCD(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long rx, ry, d = a / b;
  long long g = GCD(b, a - b * d, rx, ry);
  x = ry;
  y = rx - ry * d;
  return g;
}
void init(int u, int p) {
  sz[u] = 1;
  for (auto &e : adj[u]) {
    if (e.v != p && !removed[e.v]) {
      init(e.v, u);
      sz[u] += sz[e.v];
    }
  }
}
int centroid(int u, int p) {
  for (auto &e : adj[u]) {
    if (e.v != p && !removed[e.v] && sz[e.v] > totalSize / 2) {
      return centroid(e.v, u);
    }
  }
  return u;
}
void recalc(int u, int p) {
  for (auto &e : adj[u]) {
    if (e.v != p && !removed[e.v]) {
      depth[e.v] = depth[u] + 1;
      x[e.v] = (x[u] + e.w * pw[depth[u]]) % mod;
      y[e.v] = (y[u] * base + e.w) % mod;
      recalc(e.v, u);
    }
  }
}
void calc(int u, int p) {
  auto it = mp.find(x[u]);
  if (it != mp.end()) {
    ans += it->second;
  }
  for (auto &e : adj[u]) {
    if (e.v != p && !removed[e.v]) {
      calc(e.v, u);
    }
  }
}
void updateVal(int u, int p) {
  mp[(-y[u] + mod) * pw_inv[depth[u]] % mod]++;
  for (auto &e : adj[u]) {
    if (e.v != p && !removed[e.v]) {
      updateVal(e.v, u);
    }
  }
}
void dfs(int u, int p) {
  ans += (x[u] == 0);
  ans += (y[u] == 0);
  for (auto &e : adj[u]) {
    if (e.v != p && !removed[e.v]) {
      dfs(e.v, u);
    }
  }
}
void rec(int u) {
  init(u, -1);
  totalSize = sz[u];
  u = centroid(u, -1);
  depth[u] = 0;
  x[u] = y[u] = 0;
  recalc(u, -1);
  mp.clear();
  for (int i = 0; i < (int)(adj[u].size()); ++i) {
    if (!removed[adj[u][i].v]) {
      calc(adj[u][i].v, u);
      updateVal(adj[u][i].v, u);
    }
  }
  mp.clear();
  for (int i = (int)(adj[u].size()) - 1; i >= 0; --i) {
    if (!removed[adj[u][i].v]) {
      calc(adj[u][i].v, u);
      updateVal(adj[u][i].v, u);
    }
  }
  for (auto &e : adj[u]) {
    if (!removed[e.v]) {
      dfs(e.v, u);
    }
  }
  removed[u] = 1;
  for (auto &e : adj[u]) {
    if (!removed[e.v]) {
      rec(e.v);
    }
  }
}
void solve() {
  cin >> n >> mod;
  for (int i = 1; i <= (int)(n - 1); ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  if (mod == 1) {
    cout << (long long)n * (n - 1);
    return;
  }
  base = 10;
  GCD(base, mod, base_inv, tmp);
  base_inv = (base_inv % mod + mod) % mod;
  pw[0] = pw_inv[0] = 1;
  for (int i = 1; i <= (int)(n); ++i) {
    pw[i] = pw[i - 1] * base % mod;
    pw_inv[i] = pw_inv[i - 1] * base_inv % mod;
  }
  rec(0);
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}
