#include <bits/stdc++.h>
using namespace std;
long long len = 1e5;
long long N, M, ans = 0;
vector<long long> PP(2 * len + 5);
struct node {
  long long v, c;
};
vector<vector<node>> Adj(len);
struct CeDe : unordered_set<long long> {
  vector<long long> P, cnt;
  map<long long, long long> S1, S2, P1, P2;
  CeDe(long long n) {
    P.resize(n), cnt.resize(n);
    build(0, -1);
  }
  void build(long long u, long long p) {
    long long sz = dfs(u, u), ct = dfs(u, u, sz);
    if (p == -1) p = ct;
    P[ct] = p;
    insert(ct);
    S1.clear(), P1.clear();
    S1[0]++, P1[0]++;
    for (auto i : Adj[ct]) {
      if (find(i.v) != end()) continue;
      S2.clear(), P2.clear();
      long long j;
      j = (i.c * PP[len]) % M;
      pref(i.v, ct, len + 1, j);
      j = (i.c * PP[len - 1]) % M;
      suff(i.v, ct, len - 2, j);
      for (auto val : S2) S1[val.first] += val.second;
      for (auto val : P2) P1[val.first] += val.second;
    }
    for (auto i : Adj[ct])
      if (find(i.v) == end()) build(i.v, ct);
  }
  long long dfs(long long u, long long p) {
    cnt[u] = 1;
    for (auto i : Adj[u])
      if (i.v != p and find(i.v) == end()) cnt[u] += dfs(i.v, u);
    return cnt[u];
  }
  long long dfs(long long u, long long p, long long sz) {
    for (auto i : Adj[u])
      if (i.v != p and find(i.v) == end())
        if (cnt[i.v] > sz / 2) return dfs(i.v, u, sz);
    return u;
  }
  void pref(long long u, long long p, long long h, long long val) {
    ans += S1[(M - val) % M];
    P2[val]++;
    for (auto i : Adj[u]) {
      if (i.v == p or find(i.v) != end()) continue;
      long long j = (val + i.c * PP[h]) % M;
      pref(i.v, u, h + 1, j);
    }
    return;
  }
  void suff(long long u, long long p, long long h, long long val) {
    ans += P1[(M - val) % M];
    S2[val]++;
    for (auto i : Adj[u]) {
      if (i.v == p or find(i.v) != end()) continue;
      long long j = (val + i.c * PP[h]) % M;
      suff(i.v, u, h - 1, j);
    }
    return;
  }
};
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> N >> M;
  for (long long x = 0; x < N - 1; x++) {
    long long u, v, w;
    cin >> u >> v >> w;
    Adj[u].push_back({v, w});
    Adj[v].push_back({u, w});
  }
  PP[0] = 1 % M;
  for (long long x = 1; x <= 2 * len + 1; x++) {
    PP[x] = 10 * PP[x - 1];
    PP[x] %= M;
  }
  CeDe K(N);
  cout << ans << endl;
  return 0;
}
