#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100005;
int N, M, Now;
int Tot, Head[MaxN], Next[MaxN << 1], To[MaxN << 1], Num[MaxN << 1];
int Root, Size[MaxN], F[MaxN];
int Pow1[MaxN], Pow2[MaxN], A[MaxN], B[MaxN], Dep[MaxN];
bool Vis[MaxN];
long long X, Y, Inv, Ans;
map<int, int> Map1, Map2;
int ExGCD(int a, int b, long long &x, long long &y) {
  if (!b) {
    x = 1, y = 0;
    return a;
  }
  int d = ExGCD(b, a % b, x, y);
  long long t = x;
  x = y, y = t - a / b * y;
  return d;
}
void Add_Edge(int u, int v, int w) {
  Next[++Tot] = Head[u];
  To[Tot] = v, Num[Tot] = w;
  Head[u] = Tot;
}
void Get_Root(int u, int fa) {
  int i, v;
  Size[u] = 1, F[u] = 0;
  for (i = Head[u]; i; i = Next[i])
    if ((v = To[i]) != fa && !Vis[v]) {
      Get_Root(v, u);
      Size[u] += Size[v];
      F[u] = max(F[u], Size[v]);
    }
  F[u] = max(F[u], Now - Size[u]);
  if (F[Root] > F[u]) Root = u;
}
void Get_Size(int u, int fa) {
  int i, v;
  Size[u] = 1;
  for (i = Head[u]; i; i = Next[i])
    if ((v = To[i]) != fa && !Vis[v]) {
      Get_Size(v, u);
      Size[u] += Size[v];
    }
}
void Calc(int u, int fa) {
  int i, v;
  Ans += (A[u] == 0) + (B[u] == 0);
  Ans += Map2[(M - A[u]) % M] + Map1[1ll * B[u] * Pow2[Dep[u]] % M];
  for (i = Head[u]; i; i = Next[i])
    if ((v = To[i]) != fa && !Vis[v]) {
      A[v] = (1ll * Num[i] * Pow1[Dep[u]] % M + A[u]) % M;
      B[v] = (1ll * B[u] * 10 % M + Num[i]) % M;
      Dep[v] = Dep[u] + 1;
      Calc(v, u);
    }
}
void Update(int u, int fa, int x) {
  int i, v;
  Map1[(M - A[u]) % M] += x;
  Map2[1ll * B[u] * Pow2[Dep[u]] % M] += x;
  for (i = Head[u]; i; i = Next[i])
    if ((v = To[i]) != fa && !Vis[v]) Update(v, u, x);
}
void DFS(int u) {
  int i, v;
  Vis[u] = true;
  Get_Size(u, 0);
  for (i = Head[u]; i; i = Next[i])
    if (!Vis[v = To[i]]) {
      A[v] = B[v] = Num[i] % M;
      Dep[v] = 1;
      Calc(v, 0);
      Update(v, 0, 1);
    }
  for (i = Head[u]; i; i = Next[i])
    if (!Vis[v = To[i]]) Update(v, 0, -1);
  for (i = Head[u]; i; i = Next[i])
    if (!Vis[v = To[i]]) {
      Root = 0, Now = Size[v];
      Get_Root(v, 0);
      DFS(Root);
    }
}
int main() {
  int i, u, v, w;
  scanf("%d%d", &N, &M);
  for (i = 1; i < N; i++) {
    scanf("%d%d%d", &u, &v, &w);
    u++, v++;
    Add_Edge(u, v, w);
    Add_Edge(v, u, w);
  }
  ExGCD(10, M, X, Y);
  Inv = (X + M) % M;
  Pow1[0] = Pow2[0] = 1;
  for (i = 1; i <= N; i++) {
    Pow1[i] = 1ll * Pow1[i - 1] * 10 % M;
    Pow2[i] = 1ll * Pow2[i - 1] * Inv % M;
  }
  F[0] = 1 << 30, Now = N;
  Get_Root(1, 0);
  DFS(Root);
  printf("%I64d\n", Ans);
  return 0;
}
