#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int mod;
vector<pair<int, int> > g[N];
bool disabled[N];
int SZ[N];
long long int P[N], IP[N];
int cdComputeSizes(int c, int p) {
  SZ[c] = 1;
  for (int i = 0; i < g[c].size(); i++) {
    int u = g[c][i].first;
    if (u != p && !disabled[u]) {
      SZ[c] += cdComputeSizes(u, c);
    }
  }
  return SZ[c];
}
pair<int, int> cdGetRoot(int c, int p, int sz) {
  pair<int, int> res(-1, -1);
  int mx = sz - SZ[c];
  for (int i = 0; i < g[c].size(); i++) {
    int u = g[c][i].first;
    if (u != p && !disabled[u]) {
      mx = max(mx, SZ[u]);
      pair<int, int> tmp = cdGetRoot(u, c, sz);
      if (res.second == -1 || res.second > tmp.second) {
        res = tmp;
      }
    }
  }
  if (res.second == -1 || res.second > mx) {
    res.first = c;
    res.second = mx;
  }
  return res;
}
long long int ans = 0;
map<int, int> M;
void dfs(int c, int d, int dep, int p) {
  if (!d) {
    ans++;
  }
  M[d]++;
  for (int i = 0; i < g[c].size(); i++) {
    int u = g[c][i].first;
    if (disabled[u] || u == p) continue;
    dfs(u, (g[c][i].second * P[dep + 1] + d) % mod, dep + 1, c);
  }
}
void subDfs(int c, int d, int dep, int p) {
  M[d]--;
  for (int i = 0; i < g[c].size(); i++) {
    int u = g[c][i].first;
    if (disabled[u] || u == p) continue;
    subDfs(u, (g[c][i].second * 1LL * P[dep + 1] + d) % mod, dep + 1, c);
  }
}
void ultiDfs(int c, int d, int dep, int p) {
  if (!d) ans++;
  int tmp = ((mod - d) * 1LL * IP[dep + 1]) % mod;
  ans += M[tmp];
  for (int i = 0; i < g[c].size(); i++) {
    int u = g[c][i].first;
    if (disabled[u] || u == p) continue;
    ultiDfs(u, (d * 10LL + g[c][i].second) % mod, dep + 1, c);
  }
}
void addDfs(int c, int d, int dep, int p) {
  M[d]++;
  for (int i = 0; i < g[c].size(); i++) {
    int u = g[c][i].first;
    if (disabled[u] || u == p) continue;
    addDfs(u, (g[c][i].second * P[dep + 1] + d) % mod, dep + 1, c);
  }
}
void solve(int c) {
  int r = cdGetRoot(c, -1, cdComputeSizes(c, -1)).first;
  M.clear();
  for (int i = 0; i < g[r].size(); i++) {
    int u = g[r][i].first;
    if (disabled[u]) continue;
    dfs(u, g[r][i].second % mod, 0, r);
  }
  for (int i = 0; i < g[r].size(); i++) {
    int u = g[r][i].first;
    if (disabled[u]) continue;
    subDfs(u, g[r][i].second % mod, 0, r);
    ultiDfs(u, g[r][i].second % mod, 0, r);
    addDfs(u, g[r][i].second % mod, 0, r);
  }
  disabled[r] = true;
  for (int i = 0; i < g[r].size(); i++) {
    int u = g[r][i].first;
    if (disabled[u]) continue;
    solve(u);
  }
}
int phi(int n) {
  vector<int> p;
  int tmp = n;
  for (int i = 2; i * i <= tmp; i++)
    if (tmp % i == 0) {
      p.push_back(i);
      while (tmp % i == 0) tmp /= i;
    }
  if (tmp > 1) p.push_back(tmp);
  for (int i = 0; i < p.size(); i++) {
    n /= p[i];
    n *= p[i] - 1;
  }
  return n;
}
long long int _pow(long long int a, long long int b) {
  if (!b) return 1;
  if (b == 1) return a;
  if (b == 2) return a * a % mod;
  if (b & 1) {
    return a * _pow(a, b - 1) % mod;
  }
  return _pow(_pow(a, b / 2), 2);
}
void pre() {
  if (mod == 1) return;
  long long int inv = _pow(10, phi(mod) - 1);
  P[0] = IP[0] = 1;
  for (int i = 1; i < N; i++) {
    P[i] = P[i - 1] * 10 % mod;
    IP[i] = IP[i - 1] * inv % mod;
  }
}
int main() {
  int n;
  scanf("%d%d", &n, &mod);
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    g[u].push_back(make_pair(v, w));
    g[v].push_back(make_pair(u, w));
  }
  if (mod == 1) {
    cout << n * 1LL * (n - 1) << "\n";
    return 0;
  }
  pre();
  solve(0);
  cout << ans << "\n";
  return 0;
}
