#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5;
long long power[N];
namespace Inv {
void extgcd(long long a, long long b, long long& x, long long& y) {
  if (!b)
    x = 1, y = 0;
  else
    extgcd(b, a % b, y, x), y -= a / b * x;
}
inline long long get(long long b, long long p) {
  long long x, y;
  extgcd(b, p, x, y);
  x = (x % p + p) % p;
  return x;
}
}  // namespace Inv
long long n, m;
long long ans;
struct edge {
  long long to, len;
};
vector<edge> G[N];
long long root;
long long maxp[N], size[N];
bool centr[N];
long long getSize(long long x, long long f) {
  size[x] = 1;
  for (auto y : G[x])
    if (!centr[y.to] && y.to != f) size[x] += getSize(y.to, x);
  return size[x];
}
void getCentr(long long x, long long f, long long t) {
  maxp[x] = 0;
  for (auto y : G[x]) {
    if (centr[y.to] || y.to == f) continue;
    getCentr(y.to, x, t);
    maxp[x] = max(maxp[x], size[y.to]);
  }
  maxp[x] = max(maxp[x], t - size[x]);
  if (maxp[x] < maxp[root]) root = x;
}
vector<pair<long long, long long> > dat;
map<long long, long long> cnt;
void getData(long long x, long long f, long long dight_pos, long long dight_neg,
             long long dep) {
  if (dep >= 0) {
    cnt[dight_pos]++;
    dat.push_back(make_pair(dight_neg, dep));
  }
  for (auto y : G[x]) {
    if (centr[y.to] || y.to == f) continue;
    long long dp = (dight_pos + y.len * power[dep + 1] % m) % m;
    long long dn = (dight_neg * 10 + y.len) % m;
    getData(y.to, x, dp, dn, dep + 1);
  }
}
inline long long count(long long x, long long d) {
  long long ret = 0;
  cnt.clear(), dat.clear();
  d ? getData(x, 0, d % m, d % m, 0) : getData(x, 0, 0, 0, -1);
  for (auto p : dat) {
    long long t = (-p.first * Inv::get(power[p.second + 1], m) % m + m) % m;
    if (cnt.count(t)) ret += cnt[t];
    if (!d && p.first == 0) ++ret;
  }
  return ret + (!d ? cnt[0] : 0);
}
void solve(long long x) {
  getSize(x, 0);
  maxp[root = 0] = N;
  getCentr(x, 0, size[x]);
  long long s = root;
  centr[s] = true;
  for (auto y : G[s])
    if (!centr[y.to]) solve(y.to);
  ans += count(s, 0);
  for (auto y : G[s])
    if (!centr[y.to]) ans -= count(y.to, y.len);
  centr[s] = false;
}
signed main() {
  scanf("%lld%lld", &n, &m);
  for (register long long i = 1; i < n; i++) {
    long long u, v, l;
    scanf("%lld%lld%lld", &u, &v, &l);
    u++, v++;
    G[u].push_back(edge{v, l});
    G[v].push_back(edge{u, l});
  }
  power[0] = 1 % m;
  for (register long long i = 1; i <= n; i++) power[i] = power[i - 1] * 10 % m;
  ans = 0, solve(1);
  printf("%lld\n", ans);
}
