#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 100001;
ll PHI;
vector<pair<int, int>> adj[mxN];
vector<int> nodes;
int sz[mxN];
ll up[mxN], down[mxN];
int depth[mxN];
int subtree[mxN];
bool flag[mxN];
ll subtrees;
int maxsz;
ll n, MOD, ans;
ll modpow(ll a, ll b) {
  ll res = 1;
  while (b) {
    if (b & 1) res = (res * a) % MOD;
    a = (a * a) % MOD;
    b >>= 1;
  }
  return res;
}
ll modinv(ll a) { return modpow(a, PHI - 1); }
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;
}
int cent(int curr, int p) {
  for (auto e : adj[curr]) {
    if (flag[e.first] || e.first == p) continue;
    if (sz[e.first] * 2 > maxsz) return cent(e.first, curr);
  }
  return curr;
}
void dfs(int curr, int p) {
  if (p == -1) nodes.clear();
  sz[curr] = 1;
  nodes.push_back(curr);
  for (auto e : adj[curr]) {
    if (flag[e.first] || e.first == p) continue;
    dfs(e.first, curr);
    sz[curr] += sz[e.first];
  }
}
void go(int curr, int p, int ct) {
  if (p == ct) {
    subtree[curr] = subtrees;
    subtrees++;
  } else if (p != -1) {
    subtree[curr] = subtree[p];
  }
  for (auto e : adj[curr]) {
    if (flag[e.first] || e.first == p) continue;
    depth[e.first] = depth[curr] + 1;
    down[e.first] = (10 * down[curr] + e.second) % MOD;
    up[e.first] = (up[curr] + modpow(10, depth[curr]) * e.second) % MOD;
    ans += down[e.first] == 0;
    ans += up[e.first] == 0;
    go(e.first, curr, ct);
  }
}
void solve(int rt) {
  dfs(rt, -1);
  maxsz = sz[rt];
  for (int i : nodes) {
    up[i] = 0;
    depth[i] = 0;
    down[i] = 0;
  }
  subtrees = 0;
  int ct = cent(rt, -1);
  flag[ct] = true;
  go(ct, -1, ct);
  map<ll, ll> mp;
  map<ll, ll> all[subtrees];
  for (int i : nodes) {
    if (i == ct) continue;
    mp[up[i]]++;
    all[subtree[i]][up[i]]++;
  }
  for (int i : nodes) {
    if (i == ct) {
      continue;
    } else {
      ll need = ((-down[i] * modinv(modpow(10, depth[i])) % MOD) + MOD) % MOD;
      ans += mp[need] - all[subtree[i]][need];
    }
  }
  for (auto e : adj[ct]) {
    if (!flag[e.first]) solve(e.first);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> MOD;
  if (MOD == 1) {
    cout << (n * (n - 1)) << "\n";
    return 0;
  }
  PHI = phi(MOD);
  int a, b, c;
  for (int i = 0; i < n - 1; ++i) {
    cin >> a >> b >> c;
    adj[a].push_back({b, c});
    adj[b].push_back({a, c});
  }
  solve(0);
  cout << ans << "\n";
  return 0;
}
