#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
const long long LGN = 20;
const long long MOD = 1e9 + 7;
long long n, m, ans;
vector<pair<long long, long long> > g[N];
vector<long long> cd[N];
vector<long long> sz(N), dead(N), par(N), level(N), i10(N), p10(N);
map<long long, long long> aU, aD, um, dm;
long long down[LGN][N], up[LGN][N];
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  a %= b;
  return gcd(b, a);
}
long long mod(long long val, long long md) {
  val %= md;
  if (val < 0) val += md;
  return val;
}
long long dfs(long long u, long long v = -1) {
  sz[u] = 1;
  for (auto it : g[u]) {
    long long i = it.first;
    if (i != v && !dead[i]) sz[u] += dfs(i, u);
  }
  return sz[u];
}
long long findCentroid(long long u, long long sn, long long p = -1) {
  for (auto it : g[u]) {
    long long i = it.first;
    if (i != p && !dead[i] && sz[i] > sn / 2) return findCentroid(i, sn, u);
  }
  return u;
}
void precompute(long long c, long long lvl, long long p, long long cnt,
                long long centroid) {
  for (auto it : g[c]) {
    long long i = it.first;
    if (i != p && !dead[i]) {
      down[lvl][i] = mod(down[lvl][c] + it.second * i10[cnt], m);
      up[lvl][i] = mod(up[lvl][c] + it.second * p10[cnt], m);
      um[up[lvl][i]]++;
      dm[down[lvl][i]]++;
      precompute(i, lvl, c, cnt + 1, centroid);
    }
  }
}
long long decompose(long long u, long long v) {
  long long centroid = findCentroid(u, dfs(u));
  dead[centroid] = 1;
  par[centroid] = v;
  if (v != -1) {
    level[centroid] = level[v] + 1;
    cd[centroid].push_back(v);
    cd[v].push_back(centroid);
  }
  long long lvl = level[centroid];
  aU.clear();
  aD.clear();
  aU[0]++;
  aD[0]++;
  for (auto it : g[centroid]) {
    long long i = it.first;
    if (!dead[i]) {
      down[lvl][i] = mod(it.second, m);
      up[lvl][i] = mod(it.second, m);
      um.clear();
      dm.clear();
      um[up[lvl][i]]++;
      dm[down[lvl][i]]++;
      precompute(i, lvl, centroid, 1, centroid);
      for (auto j : um) {
        long long need = mod(-10 * j.first, m);
        if (aD.find(need) != aD.end()) {
          ans += aD[need] * j.second;
        }
      }
      for (auto j : dm) {
        long long need = mod(-i10[1] * j.first, m);
        if (aU.find(need) != aU.end()) {
          ans += aU[need] * j.second;
        }
      }
      for (auto j : um) aU[mod(j.first, m)] += j.second;
      for (auto j : dm) aD[mod(j.first, m)] += j.second;
    }
  }
  for (auto it : g[centroid]) {
    long long i = it.first;
    if (!dead[i]) decompose(i, centroid);
  }
  return centroid;
}
long long expo(long long base, long long x, long long M = MOD) {
  long long res = 1;
  base = base % M;
  while (x > 0) {
    if (x & 1) res = (res * base) % M;
    x = x >> 1;
    base = (base * base) % M;
  }
  return res;
}
long long phi(long long x) {
  long long res = x;
  for (long long i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      while (x % i == 0) x /= i;
      res /= i;
      res *= (i - 1);
    }
  }
  if (x != 1) res /= x, res *= (x - 1);
  return res;
}
void solve() {
  cin >> n >> m;
  i10[0] = 1;
  i10[1] = expo(10, phi(m) - 1, m);
  p10[0] = 1;
  p10[1] = mod(10, m);
  for (long long i = 2; i < N; i++) {
    i10[i] = mod(i10[i - 1] * i10[1], m);
    p10[i] = mod(p10[i - 1] * p10[1], m);
  }
  for (long long i = 0; i < n - 1; i++) {
    long long u, v, w;
    cin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  long long root = decompose(0, -1);
  cout << ans << endl;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  clock_t begin = clock();
  solve();
  clock_t end = clock();
  cerr << double(end - begin) / CLOCKS_PER_SEC << endl;
  return 0;
}
