#include <bits/stdc++.h>
struct edge {
  int to, nxt, val;
} E[300000];
int H[200000], tot;
void add_edge(int a, int b, int v) {
  E[++tot] = (edge){b, H[a], v};
  H[a] = tot;
  E[++tot] = (edge){a, H[b], v};
  H[b] = tot;
}
int n, P;
long long ANS;
void exgcd(int a, int b, int &X, int &Y) {
  if (!b)
    X = 1, Y = 0;
  else
    exgcd(b, a % b, Y, X), Y -= a / b * X;
}
namespace VDC {
int size[200000];
bool vis[200000];
long long Pow10[200000];
int inv;
int ROOT, SONSIZE, FULLSIZE;
void init() {
  Pow10[0] = 1;
  for (int i = 1; i <= n; i++) Pow10[i] = Pow10[i - 1] * 10 % P;
  int _;
  exgcd(10, P, inv, _);
  inv = (inv + P) % P;
}
void _getg(int now, int fa) {
  size[now] = 1;
  int NOWSIZE = 0;
  for (int i = H[now]; i; i = E[i].nxt) {
    if (E[i].to == fa || vis[E[i].to]) continue;
    _getg(E[i].to, now);
    size[now] += size[E[i].to];
    NOWSIZE = std::max(NOWSIZE, size[E[i].to]);
  }
  NOWSIZE = std::max(NOWSIZE, FULLSIZE - size[now]);
  if (SONSIZE > NOWSIZE) {
    SONSIZE = NOWSIZE;
    ROOT = now;
  }
}
int getg(int now, int fsize) {
  SONSIZE = 1 << 30;
  FULLSIZE = fsize;
  ROOT = now;
  _getg(now, 0);
  int ret = ROOT;
  _getg(ROOT, 0);
  return ret;
}
std::map<int, int> A;
void getA(int now, int fa, long long Val, int dep) {
  A[Val]++;
  for (int i = H[now]; i; i = E[i].nxt) {
    if (E[i].to == fa || vis[E[i].to]) continue;
    getA(E[i].to, now, (Val + Pow10[dep] * E[i].val) % P, dep + 1);
  }
}
long long getB(int now, int fa, long long Val, long long mul10) {
  long long ret = A[Val * mul10 % P];
  for (int i = H[now]; i; i = E[i].nxt) {
    if (E[i].to == fa || vis[E[i].to]) continue;
    ret += getB(E[i].to, now, ((Val * 10 - E[i].val) % P + P) % P,
                mul10 * inv % P);
  }
  return ret;
}
long long calc(int now, int ex, int dp) {
  A.clear();
  getA(now, 0, ex * 11 % P, dp << 1);
  return getB(now, 0, 0, 1);
}
void divide(int now) {
  ANS += calc(now, 0, 0);
  vis[now] = true;
  for (int i = H[now]; i; i = E[i].nxt) {
    if (vis[E[i].to]) continue;
    ANS -= calc(E[i].to, E[i].val, 1);
    divide(getg(E[i].to, size[E[i].to]));
  }
}
}  // namespace VDC
int main() {
  scanf("%d%d", &n, &P);
  for (int i = 1, u, v, a; i < n; i++)
    scanf("%d%d%d", &u, &v, &a), add_edge(u + 1, v + 1, a);
  VDC::init();
  VDC::divide(VDC::getg(1, n));
  printf("%lld\n", ANS - n);
}
