#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;
int n, mark[N], a[N], sz[N], mx[N], MOD, pw[N], inv[N];
long long ans;
map<int, int> m;
vector<int> V, UP[N];
vector<pair<int, int> > adj[N], DOWN[N];
int power(int a, int b) {
  if (b == 0) return 1;
  int tmp = power(a, b / 2);
  tmp = (1ll * tmp * tmp) % MOD;
  if (b % 2) tmp = (1ll * tmp * a) % MOD;
  return tmp;
}
void DFS(int v, int p) {
  V.push_back(v);
  sz[v] = 1, mx[v] = 0;
  for (auto u : adj[v]) {
    if (mark[u.first] || u.first == p) continue;
    DFS(u.first, v);
    sz[v] += sz[u.first];
    mx[v] = max(mx[v], sz[u.first]);
  }
  return;
}
int cntr(int v) {
  V.clear();
  DFS(v, 0);
  int siz = (int)V.size();
  for (auto u : V)
    if (mx[u] <= siz / 2 && siz - sz[u] <= siz / 2) return u;
  return 0;
}
void DFSC(int v, int p, int vald, int valu, int h, int in) {
  DOWN[in].push_back(make_pair(h, vald));
  UP[in].push_back(valu);
  for (auto u : adj[v]) {
    if (mark[u.first] || u.first == p) continue;
    int nvald = ((1ll * vald * 10) + u.second) % MOD;
    int nvalu = ((1ll * u.second * pw[h]) + valu) % MOD;
    DFSC(u.first, v, nvald, nvalu, h + 1, in);
  }
  return;
}
void solve(int v) {
  int c = cntr(v);
  mark[c] = 1;
  int cnt = 0;
  for (auto u : adj[c]) {
    if (mark[u.first]) continue;
    UP[cnt].clear();
    DOWN[cnt].clear();
    DFSC(u.first, c, (u.second % MOD), (u.second % MOD), 1, cnt);
    cnt++;
  }
  for (int i = 0; i < cnt; i++)
    for (auto u : UP[i]) m[u]++;
  for (int i = 0; i < cnt; i++) {
    for (auto u : UP[i]) m[u]--;
    for (auto u : DOWN[i]) {
      int x = (MOD - (u.second % MOD)) % MOD;
      x = (1ll * x * inv[u.first]) % MOD;
      ans += m[x];
    }
    for (auto u : UP[i]) m[u]++;
  }
  for (int i = 0; i < cnt; i++) {
    for (auto u : UP[i])
      if (u == 0) ans++;
    for (auto u : DOWN[i])
      if (u.second == 0) ans++;
    for (auto u : UP[i]) m[u]--;
  }
  for (auto u : adj[c]) {
    if (mark[u.first]) continue;
    solve(u.first);
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> MOD;
  if (MOD == 1) return cout << 1ll * n * (n - 1) << '\n', 0;
  int ph = MOD;
  int MODD = MOD;
  for (int i = 2; i <= sqrt(MOD); i++) {
    if (MODD % i == 0) {
      ph /= i;
      ph *= i - 1;
    }
    while (MODD % i == 0) MODD /= i;
  }
  if (MODD > 1) {
    ph /= MODD;
    ph *= MODD - 1;
  }
  pw[0] = 1, inv[0] = power(pw[0], ph - 1);
  for (int i = 1; i < N; i++)
    pw[i] = (1ll * 10 * pw[i - 1]) % MOD, inv[i] = power(pw[i], ph - 1);
  for (int i = 1, u, v, z; i < n; i++) {
    cin >> u >> v >> z;
    u++, v++;
    adj[u].push_back(make_pair(v, z));
    adj[v].push_back(make_pair(u, z));
  }
  solve(1);
  cout << ans << '\n';
  return 0;
}
