#include <bits/stdc++.h>
using namespace std;
namespace _ {
char buf[100000], *p1 = buf, *p2 = buf;
bool rEOF = 1;
inline char nc() {
  return p1 == p2 && rEOF &&
                 (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? (rEOF = 0, EOF)
             : *p1++;
}
template <class _T>
inline void read(_T& num) {
  char c = nc(), f = 1;
  num = 0;
  while (c < '0' || c > '9') c == '-' && (f = -1), c = nc();
  while (c >= '0' && c <= '9') num = num * 10 + c - '0', c = nc();
  num *= f;
}
}  // namespace _
using namespace _;
const int MAXN = 1e5 + 5;
struct Edge {
  int v, next, w;
} G[MAXN << 1];
int sz, head[MAXN];
void add(int u, int v, int w) { G[sz] = {v, head[u], w}, head[u] = sz++; }
long long n, MOD, rt, now, mx, siz[MAXN], vis[MAXN];
void getroot(int u, int fa) {
  long long tmp = 0;
  siz[u] = 1;
  for (int i = head[u]; ~i; i = G[i].next) {
    int v = G[i].v;
    if (v == fa || vis[v]) continue;
    getroot(v, u);
    siz[u] += siz[v];
    tmp = max(tmp, siz[v]);
  }
  tmp = max(tmp, now - siz[u]);
  if (tmp < mx) mx = tmp, rt = u;
}
map<long long, long long> mp;
long long ans, c[MAXN], _10[MAXN], inv_10[MAXN];
long long f(long long x, long long dep) {
  return 1ll * (MOD - x) * inv_10[dep] % MOD;
}
long long getpart(int u, int fa, long long val, int dep) {
  long long res = 0;
  for (int i = head[u]; ~i; i = G[i].next) {
    int v = G[i].v, w = G[i].w;
    if (v == fa || vis[v]) continue;
    res += getpart(v, u, (val + _10[dep] * w % MOD) % MOD, dep + 1);
  }
  res += mp[val];
  return res -= val == f(c[u], dep);
}
void getmap(int u, int fa, int dep) {
  mp[f(c[u], dep)]++;
  for (int i = head[u]; ~i; i = G[i].next) {
    int v = G[i].v, w = G[i].w;
    if (v == fa || vis[v]) continue;
    c[v] = (c[u] * 10 + w) % MOD;
    getmap(v, u, dep + 1);
  }
}
long long calc(int u, long long val, int dep) {
  val %= MOD;
  mp.clear();
  c[u] = val;
  getmap(u, 0, dep);
  return getpart(u, 0, val, dep);
}
void solve(int u) {
  vis[u] = 1, ans += calc(u, 0, 0);
  for (int i = head[u]; ~i; i = G[i].next) {
    int v = G[i].v, w = G[i].w;
    if (vis[v]) continue;
    ans -= calc(v, w, 1);
    now = mx = siz[v];
    getroot(v, v);
    solve(rt);
  }
}
void ex_gcd(long long a, long long b, long long& x, long long& y) {
  if (!b)
    x = 1, y = 0;
  else
    ex_gcd(b, a % b, y, x), y -= a / b * x;
}
long long inv(long long a, long long p) {
  long long x, y;
  ex_gcd(a, p, x, y);
  return (x + p) % p;
}
void run() {
  read(n);
  read(MOD);
  _10[0] = 1;
  for (int i = 1; i <= n; i++) head[i] = -1;
  for (int i = 1; i <= n + 1; i++) _10[i] = _10[i - 1] * 10 % MOD;
  inv_10[n + 1] = inv(_10[n + 1], MOD);
  for (int i = n + 1; i; i--) inv_10[i - 1] = inv_10[i] * 10 % MOD;
  int u, v, w;
  for (int i = 1; i < n; i++) {
    read(u);
    read(v);
    read(w);
    ++u, ++v;
    add(u, v, w), add(v, u, w);
  }
  now = mx = n;
  getroot(1, 0);
  solve(rt);
  cout << ans;
}
int main() {
  ios::sync_with_stdio(false);
  run();
  return 0;
}
