#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
bool is[N];
long long lvl[N], num[N], par[N], n, M, v1[N], v2[N], to[N], from[N],
    ans = 0, phi, dep[N];
map<long long, long long> m1, m2;
vector<long long> comp, t[N];
vector<pair<long long, long long> > g[N];
long long gp(long long a, long long b) {
  long long res = 1;
  while (b > 0)
    if (b % 2 == 0)
      b /= 2, a *= a, a %= M;
    else
      b--, res *= a, res %= M;
  return res;
}
void calc_phi(long long M) {
  phi = M;
  long long p = 2;
  long long m = M;
  while (p * p <= m) {
    while (p * p <= m && M % p != 0) p++;
    if (M % p == 0) {
      phi /= p;
      phi *= (p - 1);
      while (M % p == 0) M /= p;
    }
  }
  if (M != 1) phi /= M, phi *= (M - 1);
}
long long dfs1(long long v, long long sz, long long &center, long long p = -1) {
  long long sum = 1;
  comp.push_back(v);
  for (long long i = 0; i < g[v].size(); i++)
    if (lvl[g[v][i].first] == -1 && g[v][i].first != p)
      sum += dfs1(g[v][i].first, sz, center, v);
  if (center == -1 && 2 * sum >= sz) center = v;
  return sum;
}
void build(long long v, long long dep, long long p = 0) {
  long long center = -1, tmp = -1;
  long long sz = dfs1(v, tmp, tmp);
  comp.clear();
  dfs1(v, sz, center);
  lvl[center] = dep;
  par[center] = p;
  t[center] = comp;
  for (long long i = 0; i < g[center].size(); i++)
    if (lvl[g[center][i].first] == -1)
      build(g[center][i].first, dep + 1, center);
}
void dfs2(long long v, long long p = -1, long long up = 0, long long down = 0,
          long long part = -1, long long h = 0) {
  v1[v] = up;
  v2[v] = down;
  dep[v] = h;
  num[v] = part;
  for (long long i = 0; i < g[v].size(); i++)
    if (is[g[v][i].first] && g[v][i].first != p) {
      long long p1 = part;
      if (part == -1) p1 = i;
      long long up1 = up, down1 = down;
      long long x = g[v][i].second;
      down1 *= 10;
      down1 += x;
      down1 %= M;
      up1 += gp(10, h) * x % M;
      up1 %= M;
      dfs2(g[v][i].first, v, up1, down1, p1, h + 1);
    }
}
void solve(long long center) {
  m1.clear();
  m2.clear();
  for (long long i = 0; i < t[center].size(); i++) is[t[center][i]] = 1;
  dfs2(center);
  vector<map<long long, long long> > sub;
  sub.resize(g[center].size());
  map<long long, long long> kol;
  for (long long i = 0; i < t[center].size(); i++) {
    long long u = t[center][i];
    if (u != center) {
      sub[num[u]][v1[u]]++;
      kol[v1[u]]++;
    }
  }
  ans += kol[0];
  for (long long i = 0; i < t[center].size(); i++)
    if (v2[t[center][i]] == 0) ans++;
  ans--;
  for (long long i = 0; i < t[center].size(); i++) {
    long long u = t[center][i];
    if (u != center) {
      long long want = (-v2[u] * gp(gp(10, phi - 1), dep[u]) % M) + M;
      want %= M;
      ans += kol[want] - sub[num[u]][want];
    }
  }
  for (long long i = 0; i < t[center].size(); i++) is[t[center][i]] = 0;
}
signed main() {
  cin >> n >> M;
  calc_phi(M);
  for (long long i = 1; i <= n; i++) lvl[i] = -1;
  for (long long i = 1; i < n; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    a++;
    b++;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  build(1, 1);
  for (long long i = 1; i <= n; i++) solve(i);
  cout << ans << endl;
  return 0;
}
