#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
using ll = long long;
using pii = pair<ll, int>;
const int INF = 1e9 + 1e2;
void fin() {}
const bool flag = 0;
const int N = 1e5 + 10;
int MOD;
int mult(ll a, ll b) { return a * 1ll * b % MOD; }
ll binpow(ll a, int b) {
  ll res = 1;
  while (b) {
    if (b & 1) {
      res = mult(res, a);
    }
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}
vector<pii> adj[N];
int sz[N], po[N];
bool cent[N];
void calc_sz(int first, int p = -1) {
  sz[first] = 1;
  for (pii to : adj[first]) {
    if (to.first != p && !cent[to.first]) {
      calc_sz(to.first, first);
      sz[first] += sz[to.first];
    }
  }
}
int c_sz;
int fnd(int first, int p = -1) {
  for (pii to : adj[first]) {
    if (to.first != p && !cent[to.first] && sz[to.first] > c_sz / 2) {
      return fnd(to.first, first);
    }
  }
  return first;
}
ll ans;
int add(ll a, int b) { return (a + b + MOD) % MOD; }
map<int, ll> cnt;
void dfsadd(int first, int d, int r, int p = -1) {
  cnt[r]++;
  for (pii to : adj[first]) {
    if (to.first != p && !cent[to.first]) {
      dfsadd(to.first, d + 1, add(r, mult(po[d], to.second)), first);
    }
  }
}
void dfscalc(int first, int d, int r1, int r2, int p = -1) {
  ans += (r1 == 0) + (r2 == 0);
  for (pii to : adj[first]) {
    if (to.first != p && !cent[to.first]) {
      dfscalc(to.first, d + 1, add(mult(r1, 10), to.second),
              add(r2, mult(po[d], to.second)), first);
    }
  }
}
int phi;
void dfsget(int first, int d, int r, int p = -1) {
  int inv = mult(MOD - r, binpow(po[d], phi - 1));
  ans += cnt[inv];
  for (pii to : adj[first]) {
    if (to.first != p && !cent[to.first]) {
      dfsget(to.first, d + 1, add(mult(r, 10), to.second), first);
    }
  }
}
void solve(int first = 0) {
  calc_sz(first);
  c_sz = sz[first];
  first = fnd(first);
  cent[first] = 1;
  for (pii to : adj[first]) {
    if (!cent[to.first]) {
      dfsget(to.first, 1, to.second);
      dfsadd(to.first, 1, to.second);
      dfscalc(to.first, 1, to.second, to.second);
    }
  }
  cnt.clear();
  reverse((adj[first]).begin(), (adj[first]).end());
  for (pii to : adj[first]) {
    if (!cent[to.first]) {
      dfsget(to.first, 1, to.second);
      dfsadd(to.first, 1, to.second);
    }
  }
  cnt.clear();
  for (pii to : adj[first]) {
    if (!cent[to.first]) {
      solve(to.first);
    }
  }
}
void ma1n() {
  int n;
  cin >> n >> MOD;
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    w %= MOD;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  int first = MOD;
  phi = MOD;
  for (int i = 2; i <= sqrt(first); ++i) {
    if (first % i == 0) {
      while (first % i == 0) {
        first /= i;
      }
      phi -= phi / i;
    }
  }
  if (first > 1) {
    phi -= phi / first;
  }
  po[0] = 1;
  for (int i = 1; i < N; ++i) {
    po[i] = mult(po[i - 1], 10);
  }
  solve();
  cout << ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr), fin();
  int ts = 1;
  if (flag) {
    cin >> ts;
  }
  while (ts--) {
    ma1n();
  }
  return 0;
}
