#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 50;
const int inf = 0x3f3f3f3f;
int n, mod;
long long ans;
int head[maxn], nxt[maxn << 1], to[maxn << 1], cost[maxn << 1], edge_tot;
void add_edge(int u, int v, int c) {
  nxt[++edge_tot] = head[u];
  head[u] = edge_tot;
  to[edge_tot] = v;
  cost[edge_tot] = c;
}
void change(long long &x, int mod) { x = (x % mod + mod) % mod; }
void ext_gcd(long long a, long long b, long long &d, long long &x,
             long long &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    ext_gcd(b, a % b, d, y, x);
    y -= x * (a / b);
  }
}
long long fac[maxn], inv[maxn];
void pre() {
  fac[0] = 1;
  for (int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * 10 % mod;
  for (int i = 0; i < maxn; i++) {
    long long a = fac[i], b = mod;
    long long d, x, y;
    ext_gcd(a, b, d, x, y);
    change(x, mod);
    inv[i] = x;
  }
}
int root;
bool vis[maxn];
int siz[maxn], mxson[maxn];
void ndc_init() { mxson[0] = inf; }
void get_root(int u, int f, int sum) {
  siz[u] = 1;
  mxson[u] = 0;
  for (int i = head[u]; i; i = nxt[i]) {
    int v = to[i];
    if (vis[v] || v == f) continue;
    get_root(v, u, sum);
    siz[u] += siz[v];
    if (mxson[u] < siz[v]) mxson[u] = siz[v];
  }
  if (mxson[u] < sum - siz[u]) mxson[u] = sum - siz[u];
  if (mxson[u] < mxson[root]) root = u;
}
map<long long, int> mp;
void add1(int u, int f, register long long sum, int dep, int op) {
  mp[sum] += op;
  for (int i = head[u]; i; i = nxt[i]) {
    int v = to[i];
    if (vis[v] || v == f) continue;
    add1(v, u, (sum + fac[dep] * cost[i] % mod) % mod, dep + 1, op);
  }
}
void calc(int u, int f, register long long sum, int dep) {
  if (!sum) ans++;
  long long fd = -inv[dep] * sum;
  change(fd, mod);
  if (mp.count(fd)) ans += mp[fd];
  for (int i = head[u]; i; i = nxt[i]) {
    int v = to[i];
    if (vis[v] || v == f) continue;
    calc(v, u, (sum * 10 + cost[i]) % mod, dep + 1);
  }
}
void solve(int u = 1, int sum = n) {
  root = 0;
  get_root(u, 0, sum);
  vis[root] = 1;
  for (int i = head[root]; i; i = nxt[i]) {
    int v = to[i];
    if (vis[v]) continue;
    add1(v, root, cost[i] % mod, 1, 1);
  }
  if (mp.count(0)) ans += mp[0];
  for (int i = head[root]; i; i = nxt[i]) {
    int v = to[i];
    if (vis[v]) continue;
    add1(v, root, cost[i] % mod, 1, -1);
    calc(v, root, cost[i] % mod, 1);
    add1(v, root, cost[i] % mod, 1, 1);
  }
  mp.clear();
  int root_sz = siz[root];
  for (int i = head[root]; i; i = nxt[i]) {
    int v = to[i];
    if (vis[v]) continue;
    solve(v, siz[v]);
  }
}
int main() {
  ans = 0;
  scanf("%d%d", &n, &mod);
  for (int i = 1; i < n; i++) {
    int u, v, c;
    scanf("%d%d%d", &u, &v, &c);
    u++, v++;
    add_edge(u, v, c);
    add_edge(v, u, c);
  }
  pre();
  ndc_init();
  solve();
  printf("%lld\n", ans);
  return 0;
}
