#include <bits/stdc++.h>
using namespace std;
struct st {
  long long v, e;
  st() {}
  st(long long A, long long B) { v = A, e = B; }
};
vector<st> G[200005];
long long n, mod;
long long quickmod(long long x, long long y) {
  long long ans = 1;
  while (y) {
    if (y & 1) ans = (ans * x) % mod;
    x = (x * x) % mod;
    y >>= 1;
  }
  return ans;
}
long long siz[200005], son[200005], quick[200005], ans = 0;
long long q[200005], tot = 0;
long long vis[200005];
void get_siz(long long x, long long fa) {
  siz[x] = 1;
  for (long long i = 0; i < G[x].size(); i++) {
    long long y = G[x][i].v;
    if (y == fa || vis[y]) continue;
    get_siz(y, x);
    siz[x] += siz[y];
  }
}
long long mx, root = 0;
void get_root(long long x, long long fa, long long all) {
  long long _max = 0;
  for (long long i = 0; i < G[x].size(); i++) {
    long long y = G[x][i].v;
    if (y == fa || vis[y]) continue;
    get_root(y, x, all);
    _max = max(_max, siz[y]);
  }
  _max = max(_max, all - siz[x]);
  if (_max < mx) mx = _max, root = x;
}
map<long long, long long> M;
long long p[200005], inv[200005];
void get_son(long long x, long long fa, long long val, long long dep) {
  M[val]++;
  for (long long i = 0; i < G[x].size(); i++) {
    long long y = G[x][i].v;
    if (y == fa || vis[y]) continue;
    get_son(y, x, (quick[dep] * G[x][i].e % mod + val) % mod, dep + 1);
  }
}
void del(long long x, long long fa, long long val, long long dep) {
  M[val]--;
  for (long long i = 0; i < G[x].size(); i++) {
    long long y = G[x][i].v;
    if (y == fa || vis[y]) continue;
    del(y, x, (quick[dep] * G[x][i].e % mod + val) % mod, dep + 1);
  }
}
void add(long long x, long long fa, long long val, long long val2,
         long long dep) {
  p[++tot] = val;
  ans += M[((mod - val2) * inv[dep]) % mod];
  for (long long i = 0; i < G[x].size(); i++) {
    long long y = G[x][i].v;
    if (y == fa || vis[y]) continue;
    add(y, x, (quick[dep] * G[x][i].e % mod + val) % mod,
        (val2 * 10 % mod + G[x][i].e) % mod, dep + 1);
  }
}
void get_ans(long long x) {
  get_siz(x, x);
  mx = root = 1e9;
  get_root(x, x, siz[x]);
  x = root;
  vis[x] = 1;
  M.clear();
  M[0] = 1;
  for (long long T = 0; T < G[x].size(); T++) {
    long long y = G[x][T].v;
    if (vis[y]) continue;
    get_son(y, x, G[x][T].e % mod, 1);
  }
  for (long long T = 0; T < G[x].size(); T++) {
    long long y = G[x][T].v;
    if (vis[y]) continue;
    del(y, x, G[x][T].e % mod, 1);
    tot = 0;
    add(y, x, G[x][T].e % mod, G[x][T].e % mod, 1);
    for (long long i = 1; i <= tot; i++) {
      if (p[i] == 0) ans++;
      M[p[i]]++;
    }
  }
  for (long long i = 0; i < G[x].size(); i++) {
    long long y = G[x][i].v;
    if (vis[y]) continue;
    get_ans(y);
  }
}
long long x, y;
void ex_gcd(long long a, long long b) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  ex_gcd(b, a % b);
  long long tmp = x;
  x = y;
  y = tmp - a / b * y;
}
long long niyuan(long long n, long long p) {
  ex_gcd(n, p);
  return (x + p) % p;
}
signed main() {
  scanf("%lld %lld", &n, &mod);
  for (long long i = 1; i < n; i++) {
    long long u, v, e;
    scanf("%lld %lld %lld", &u, &v, &e);
    u++, v++;
    G[u].push_back(st(v, e));
    G[v].push_back(st(u, e));
  }
  quick[0] = 1;
  for (long long i = 1; i <= n; i++) quick[i] = (quick[i - 1] * 10) % mod;
  inv[0] = 1;
  for (long long i = 1; i <= n; i++) {
    inv[i] = niyuan(quick[i], mod);
  }
  get_ans(1);
  printf("%lld", ans);
  return 0;
}
