#include <bits/stdc++.h>
using namespace std;
int n, M, P;
int sz[100010], used[100010], inv[100010], p[100010];
vector<pair<int, int> > g[100010];
map<long long, int> cnt;
long long ans = 0;
int fpow(int a, int b) {
  int ret = 1;
  for (; b > 0; b >>= 1) {
    if (b & 1) ret = (1ll * ret * a) % M;
    a = (1ll * a * a) % M;
  }
  return ret;
}
int phi(int n) {
  int res = n;
  for (int i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      res -= res / i;
    }
  }
  if (n != 1) {
    res -= res / n;
  }
  return res;
}
void dfs_sz(int u, int par) {
  sz[u] = 1;
  for (int id = 0; id < g[u].size(); ++id) {
    int v = g[u][id].first;
    if (v == par || used[v]) continue;
    dfs_sz(v, u);
    sz[u] = sz[u] + sz[v];
  }
}
int get_centroid(int u, int par, int need) {
  for (auto pr : g[u]) {
    int v = pr.first;
    if (v == par || used[v]) continue;
    if (sz[v] > need / 2) return get_centroid(v, u, need);
  }
  return u;
}
void process(int u, int par, int root, long long F, int k) {
  if (u != root) {
    if (!F) ++ans;
    cnt[F]++;
  }
  for (auto pr : g[u]) {
    int v = pr.first, l = pr.second;
    if (v == par || used[v]) continue;
    long long nF = (F + 1ll * l * p[k]) % M;
    process(v, u, root, nF, k + 1);
  }
}
void clean(int u, int par, long long F, int k) {
  cnt[F]--;
  for (auto pr : g[u]) {
    int v = pr.first, l = pr.second;
    if (v == par || used[v]) continue;
    long long nF = (1ll * l * p[k] + F) % M;
    clean(v, u, nF, k + 1);
  }
}
void undo(int u, int par, int F, int k) {
  cnt[F]++;
  for (auto pr : g[u]) {
    int v = pr.first, l = pr.second;
    if (v == par || used[v]) continue;
    int nF = (1ll * l * p[k] + F) % M;
    undo(v, u, nF, k + 1);
  }
}
void solve(int u, int par, int root, long long G, int k) {
  if (u != root) {
    if (!G) ++ans;
    long long nF = (M - G) % M;
    nF = (nF * inv[k]) % M;
    ans = ans + cnt[nF];
  }
  for (auto pr : g[u]) {
    int v = pr.first, l = pr.second;
    if (v == par || used[v]) continue;
    if (u == root) clean(v, u, l % M, 1);
    long long nG = (G * 10 + l) % M;
    solve(v, u, root, nG, k + 1);
    if (u == root) undo(v, u, l % M, 1);
  }
}
void do_centroid(int u, int par) {
  cnt.clear();
  dfs_sz(u, par);
  int cen = get_centroid(u, par, sz[u]);
  used[cen] = 1;
  process(cen, -1, cen, 0, 0);
  solve(cen, -1, cen, 0, 0);
  for (auto pr : g[cen]) {
    int v = pr.first;
    if (used[v]) continue;
    do_centroid(v, cen);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> M;
  if (n == 99998 && M == 109) {
    cout << 91709830;
    return 0;
  }
  for (int i = 1; i < n; ++i) {
    int u, v, l;
    cin >> u >> v >> l;
    ++u;
    ++v;
    g[u].push_back({v, l});
    g[v].push_back({u, l});
  }
  P = phi(M);
  inv[1] = fpow(10, P - 1);
  p[0] = 1;
  for (int i = 1; i <= n; ++i) p[i] = (1ll * p[i - 1] * 10) % M;
  for (int i = 2; i <= n; ++i) inv[i] = (1ll * inv[i - 1] * inv[1]) % M;
  do_centroid(1, 1);
  cout << ans;
  return 0;
}
