#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void rd(T &x) {
  x = 0;
  char c;
  int f = 1;
  while (c = getchar(), c < 48)
    if (c == '-') f = -1;
  do x = x * 10 + (c & 15);
  while (c = getchar(), c > 47);
  x *= f;
}
template <class T>
void pf(T x) {
  if (x < 0)
    putchar('-'), x = -x;
  else if (!x) {
    putchar('0');
    return;
  }
  static int stk[100], tp;
  for (tp = 0; x; x /= 10) stk[tp++] = x % 10;
  while (tp) putchar(stk[--tp] ^ 48);
}
template <class T>
void ptn(T x) {
  pf(x), putchar('\n');
}
template <class T>
void ptk(T x) {
  pf(x), putchar(' ');
}
template <class T>
void Min(T &A, T B) {
  if (A > B) A = B;
}
template <class T>
void Max(T &A, T B) {
  if (A < B) A = B;
}
const int N = (int)1e5 + 5;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
struct ss {
  int to, val, nxt;
} G[N << 2];
int head[N], sz[N], son[N], Basic[N << 1];
inline void add_edge(int x, int y, int z) {
  static int edge_tot;
  G[edge_tot] = (ss){y, z, head[x]};
  head[x] = edge_tot++;
  G[edge_tot] = (ss){x, z, head[y]};
  head[y] = edge_tot++;
}
int n, mod, inv_mod, Lpos[N], Rpos[N], Mp[N];
int dpUp[N], dpDown[N], dep[N];
long long ans;
int mul(int x) { return Basic[x + N]; }
int dfs_pre(int x, int par) {
  static int dfs_clock;
  sz[x] = 1;
  son[x] = -1;
  Lpos[x] = ++dfs_clock;
  Mp[dfs_clock] = x;
  for (int i = head[x]; ~i; i = G[i].nxt) {
    int y = G[i].to;
    if (y == par) continue;
    dpDown[y] = ((long long)dpDown[x] * 10 + G[i].val) % mod;
    dpUp[y] = (dpUp[x] + G[i].val * (long long)mul(dep[x])) % mod;
    dep[y] = dep[x] + 1;
    sz[x] += dfs_pre(y, x);
    if (!~son[x] || sz[son[x]] < sz[y]) son[x] = y;
  }
  Rpos[x] = dfs_clock + 1;
  return sz[x];
}
map<int, int> Up, Down;
map<int, int>::iterator it;
int anc;
void work(int x) {
  int res =
      ((dpUp[anc] - dpDown[x] * (long long)mul((dep[anc] << 1) - dep[x]) % mod +
        dpDown[anc] * (long long)mul(dep[anc]) % mod) %
           mod +
       mod) %
      mod;
  it = Up.find(res);
  if (it != Up.end()) ans += it->second;
  res = (((dpUp[anc] - dpUp[x]) * (long long)mul(-dep[anc]) % mod *
              mul(-dep[anc]) +
          dpDown[anc] * (long long)mul(-dep[anc])) %
             mod +
         mod) %
        mod;
  it = Down.find(res);
  if (it != Down.end()) ans += it->second;
}
void calc(int x) {
  for (int i = (Lpos[x]), _t = (Rpos[x]); i < _t; ++i) work(Mp[i]);
}
void add(int x) {
  for (int i = (Lpos[x]), _t = (Rpos[x]); i < _t; ++i) {
    int id = Mp[i];
    Up[dpUp[id]]++;
    Down[dpDown[id] * (long long)mul(-dep[id]) % mod]++;
  }
}
void solve(int x, int par) {
  for (int i = head[x]; ~i; i = G[i].nxt) {
    int y = G[i].to;
    if (y == par || y == son[x]) continue;
    solve(y, x);
    Up.clear(), Down.clear();
  }
  if (~son[x]) solve(son[x], x);
  anc = x;
  for (int i = head[x]; ~i; i = G[i].nxt) {
    int y = G[i].to;
    if (y == par || y == son[x]) continue;
    calc(y);
    add(y);
  }
  work(x);
  Up[dpUp[x]]++;
  Down[dpDown[x] * (long long)mul(-dep[x]) % mod]++;
}
int main() {
  memset(head, -1, sizeof head);
  rd(n);
  rd(mod);
  if (mod == 1) {
    ptn((long long)n * (n - 1));
    return 0;
  }
  {
    long long x, y;
    extgcd(10, mod, x, y);
    inv_mod = (x % mod + mod) % mod;
  }
  Basic[N] = 1;
  for (int x, y, z, i = 1; i < n; ++i) {
    rd(x);
    rd(y);
    rd(z);
    add_edge(x, y, z);
    Basic[i + N] = (long long)Basic[i + N - 1] * 10 % mod;
  }
  for (int i = (N)-1, _s = (0); i >= _s; --i)
    Basic[i] = (long long)Basic[i + 1] * inv_mod % mod;
  dfs_pre(0, -1);
  solve(0, -1);
  ptn(ans);
  return 0;
}
