#include <bits/stdc++.h>
using namespace std;
int head[100005], tot, all;
int n, sz[100005], rt, w[100005];
long long dis[100005], DIS[100005], p[100005], ans, m, inv[100005];
bool mk[100005];
map<long long, int> mp;
struct name {
  int id, nx;
  long long v;
} to[100005 << 1];
void add(int x, int y, long long z) {
  to[++tot] = (name){y, head[x], z};
  head[x] = tot;
}
void getrt(int x, int f) {
  sz[x] = 1;
  w[x] = 0;
  for (int i = head[x]; i; i = to[i].nx) {
    int y = to[i].id;
    if (y == f || mk[y]) continue;
    getrt(y, x);
    sz[x] += sz[y];
    if (w[x] < sz[y]) w[x] = sz[y];
  }
  w[x] = max(w[x], all - sz[x]);
  if (w[x] < w[rt]) rt = x;
}
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 get(int nw) {
  long long w = p[nw], x, y;
  ex_gcd(w, m, x, y);
  return (x % m + m) % m;
}
void getdis(int x, int f, int dep, long long w) {
  for (int i = head[x]; i; i = to[i].nx) {
    int y = to[i].id;
    long long v = to[i].v;
    if (mk[y] || y == f) continue;
    dis[y] = (10 * dis[x] + v) % m;
    DIS[y] = (p[dep] * v % m + w) % m;
    getdis(y, x, dep + 1, DIS[y]);
  }
  if (dep) {
    mp[DIS[x]]++;
    if (!dis[x]) ans++;
    if (!DIS[x]) ans++;
  }
}
void getdel(int x, int f) {
  mp[DIS[x]]--;
  for (int i = head[x]; i; i = to[i].nx) {
    int y = to[i].id;
    if (mk[y] || y == f) continue;
    getdel(y, x);
  }
}
void getup(int x, int f) {
  mp[DIS[x]]++;
  for (int i = head[x]; i; i = to[i].nx) {
    int y = to[i].id;
    if (mk[y] || y == f) continue;
    getup(y, x);
  }
}
void getans(int x, int f, int dep) {
  long long need = (-dis[x] * inv[dep] % m + m) % m;
  if (mp.count(need)) ans += mp[need];
  for (int i = head[x]; i; i = to[i].nx) {
    int y = to[i].id;
    if (y == f || mk[y]) continue;
    getans(y, x, dep + 1);
  }
}
void solve(int x) {
  mk[x] = 1;
  dis[x] = DIS[x] = 0;
  getdis(x, 0, 0, 0);
  for (int i = head[x]; i; i = to[i].nx) {
    int y = to[i].id;
    if (mk[y]) continue;
    getdel(y, x);
    getans(y, x, 1);
    getup(y, x);
  }
  mp.clear();
  for (int i = head[x]; i; i = to[i].nx) {
    int y = to[i].id;
    if (mk[y]) continue;
    rt = 0;
    all = sz[y];
    getrt(y, x);
    solve(rt);
  }
}
int main() {
  scanf("%d%lld", &n, &m);
  p[0] = 1;
  for (int i = (1), _en = (n); i <= _en; i++) {
    p[i] = p[i - 1] * 10 % m;
    inv[i] = get(i);
  }
  for (int i = (2), _en = (n); i <= _en; i++) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    x++, y++;
    add(x, y, z);
    add(y, x, z);
  }
  all = n;
  w[0] = 1e9, rt = 0;
  getrt(1, 0);
  solve(rt);
  printf("%lld\n", ans);
  return 0;
}
