#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int mo = 1000000007;
const int inf = 0x3f3f3f3f;
const int INF = 2000000000;
int n, m, phi;
int lt[100008], size[100008], f[100008], vis[100008], a[100008], b[100008], sum,
    tot, root, pre1[100008], pre2[100008];
long long ans, Alltmp;
map<int, int> mp;
struct edge {
  int u, v, w, nt;
} eg[100008 * 2];
void add(int u, int v, int w) {
  eg[++sum] = (edge){u, v, w, lt[u]};
  lt[u] = sum;
}
long long quick(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y & 1) res = res * x % m;
    x = x * x % m;
    y >>= 1;
  }
  return res;
}
void init() {
  int mm = m;
  phi = m;
  for (int i = 2; i * i <= m; i++) {
    if (mm % i == 0) {
      while (mm % i == 0) mm /= i;
      phi = phi / i * (i - 1);
    }
  }
  if (mm > 1) phi = phi / mm * (mm - 1);
  memset(lt, 0, sizeof(lt));
  ;
  sum = 1;
  memset(f, 0, sizeof(f));
  ;
  f[0] = INF;
  memset(vis, 0, sizeof(vis));
  ;
  ans = 0;
  pre1[0] = 1;
  pre2[0] = 1;
  for (int i = 1; i <= 100000; i++) {
    pre1[i] = 1ll * pre1[i - 1] * 10 % m;
    pre2[i] = quick(pre1[i], phi - 1);
  }
}
void getRoot(int u, int fa) {
  size[u] = 1;
  f[u] = 0;
  for (int i = lt[u]; i; i = eg[i].nt) {
    int v = eg[i].v;
    if (vis[v] || v == fa) continue;
    getRoot(v, u);
    size[u] += size[v];
    f[u] = max(f[u], size[v]);
  }
  f[u] = max(f[u], tot - size[u]);
  if (f[u] < f[root]) root = u;
}
void getA(int u, int fa, int len) {
  for (int i = lt[u]; i; i = eg[i].nt) {
    int v = eg[i].v;
    if (vis[v] || v == fa) continue;
    a[v] = (1ll * eg[i].w * pre1[len] + a[u]) % m;
    getA(v, u, len + 1);
  }
  Alltmp += mp[a[u]];
  int tp = (m - b[u]) % m;
  tp = 1ll * tp * pre2[len] % m;
  if (a[u] == tp) Alltmp--;
}
void getB(int u, int fa, int len) {
  int tp = (m - b[u]) % m;
  tp = 1ll * tp * pre2[len] % m;
  mp[tp]++;
  for (int i = lt[u]; i; i = eg[i].nt) {
    int v = eg[i].v;
    if (vis[v] || v == fa) continue;
    b[v] = (1ll * b[u] * 10 + eg[i].w) % m;
    getB(v, u, len + 1);
  }
}
long long calc(int u, int key) {
  key %= m;
  Alltmp = 0;
  mp.clear();
  a[u] = b[u] = key;
  getB(u, 0, key == 0 ? 0 : 1);
  getA(u, 0, key == 0 ? 0 : 1);
  return Alltmp;
}
void solve(int u) {
  ans += calc(u, 0);
  vis[u] = 1;
  for (int i = lt[u]; i; i = eg[i].nt) {
    int v = eg[i].v;
    if (vis[v]) continue;
    ans -= calc(v, eg[i].w);
    root = 0;
    tot = size[v];
    getRoot(v, u);
    solve(root);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  init();
  for (int i = 1; i <= n - 1; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    add(u + 1, v + 1, w);
    add(v + 1, u + 1, w);
  }
  root = 0;
  tot = n;
  getRoot(1, 0);
  solve(root);
  cout << ans << endl;
}
