#include <bits/stdc++.h>
using namespace std;
map<long long, long long> mp, mpr;
long long n, m, d[100015], up[100015], down[100015], ans;
bool mk[100015];
long long h[100015], siz[100015];
vector<pair<long long, long long> > g[100015];
void dfs(long long v, long long p) {
  if (p != -1) h[v] = h[p] + 1;
  siz[v] = 1;
  mp[up[v]]++;
  for (auto it : g[v]) {
    if (it.first == p || mk[it.first]) continue;
    up[it.first] = (up[v] + (it.second * d[h[v]]) % m) % m;
    down[it.first] = ((down[v] * 10) % m + it.second) % m;
    dfs(it.first, v);
    siz[v] += siz[it.first];
  }
}
long long fnd_cent(long long v, long long p) {
  if (p != -1) {
    siz[p] -= siz[v];
    siz[v] += siz[p];
  }
  bool gd = 1;
  for (auto it : g[v])
    if (siz[it.first] > siz[v] / 2) {
      gd = 0;
      break;
    }
  if (gd) return v;
  for (auto it : g[v]) {
    if (it.first == p || mk[it.first]) continue;
    long long root = fnd_cent(it.first, v);
    if (root != -1) return root;
  }
  return -1;
}
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long g = gcd(b % a, a, x1, y1);
  y = x1;
  x = y1 - (b / a) * x1;
  return g;
}
void spusk(long long v, long long p) {
  mpr[up[v]]++;
  if (down[v] == 0) ans++;
  if (up[v] == 0) ans++;
  for (auto it : g[v]) {
    if (it.first == p || mk[it.first]) continue;
    spusk(it.first, v);
  }
}
void calc(long long v, long long p) {
  long long x, y;
  long long w = gcd(d[h[v]], m, x, y);
  x = (x % m + m) % m;
  long long upr = ((-down[v] * x) % m + m) % m;
  ans += mp[upr];
  ans -= mpr[upr];
  for (auto it : g[v]) {
    if (it.first == p || mk[it.first]) continue;
    calc(it.first, v);
  }
}
void rec(long long v) {
  mk[v] = 1;
  for (auto it : g[v]) {
    if (mk[it.first]) continue;
    mpr.clear();
    mpr[up[v]]++;
    spusk(it.first, v);
    calc(it.first, v);
  }
  for (auto it : g[v]) {
    if (mk[it.first]) continue;
    long long root = fnd_cent(it.first, -1);
    if (root == -1) continue;
    up[root] = down[root] = h[root] = 0;
    mp.clear();
    siz[v] = 0;
    dfs(root, -1);
    rec(root);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  istream::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (long long i = 1; i < n; i++) {
    long long x, y, z;
    cin >> x >> y >> z;
    g[x].push_back({y, z});
    g[y].push_back({x, z});
  }
  d[0] = 1;
  for (long long i = 1; i <= n; i++) d[i] = (d[i - 1] * 10) % m;
  dfs(0, -1);
  long long root = fnd_cent(0, -1);
  up[root] = down[root] = h[root] = 0;
  mp.clear();
  ans = 0;
  dfs(root, -1);
  rec(root);
  cout << ans << endl;
}
