#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
template <typename T>
inline void read(T &AKNOI) {
  T x = 0, flag = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') flag = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  AKNOI = flag * x;
}
int n;
int vis[MAXN], siz[MAXN], son[MAXN], tsiz, root;
long long M, dx[MAXN], dy[MAXN], pw[MAXN], pinv[MAXN], ans;
map<long long, int> mp1, mp2;
struct Edge {
  int v, w, nxt;
} e[MAXN << 1];
int first[MAXN], eCnt;
inline void AddEdge(int u, int v, int w) {
  e[++eCnt].v = v;
  e[eCnt].w = w;
  e[eCnt].nxt = first[u];
  first[u] = eCnt;
}
void Extend_gcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  Extend_gcd(b, a % b, y, x);
  y -= a / b * x;
}
inline long long Inv(long long a) {
  long long x, y;
  Extend_gcd(a, M, x, y);
  return (x % M + M) % M;
}
void GetRoot(int u, int fa) {
  siz[u] = 1;
  son[u] = 0;
  for (int i = first[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa || vis[v]) continue;
    GetRoot(v, u);
    son[u] = max(son[u], siz[v]);
    siz[u] += siz[v];
  }
  son[u] = max(son[u], tsiz - siz[u]);
  if (son[u] < son[root]) root = u;
}
int stk[MAXN], top;
void GetAns(int u, int fa, long long x, long long y, int dep) {
  dx[stk[++top] = u] = x;
  dy[u] = (M - y * pinv[dep] % M) % M;
  ans += (x == 0) + (y == 0);
  ans += mp2[x] + mp1[dy[u]];
  for (int i = first[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa || vis[v]) continue;
    GetAns(v, u, (pw[dep] * e[i].w + x) % M, (y * 10 + e[i].w) % M, dep + 1);
  }
}
void Point_DC(int u) {
  vis[u] = 1;
  mp1.clear();
  mp2.clear();
  for (int i = first[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (vis[v]) continue;
    GetAns(v, u, e[i].w % M, e[i].w % M, 1);
    while (top) {
      ++mp1[dx[stk[top]]];
      ++mp2[dy[stk[top--]]];
    }
  }
  for (int i = first[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (vis[v]) continue;
    tsiz = siz[v];
    root = 0;
    GetRoot(v, 0);
    Point_DC(root);
  }
}
void init() {
  read(n);
  read(M);
  for (int i = 1, u, v, w; i < n; ++i) {
    read(u);
    read(v);
    read(w);
    ++u;
    ++v;
    AddEdge(u, v, w);
    AddEdge(v, u, w);
  }
  pw[0] = pinv[0] = 1;
  for (int i = 1; i <= n; ++i) {
    pw[i] = pw[i - 1] * 10 % M;
    pinv[i] = Inv(pw[i]);
  }
}
void solve() {
  son[0] = tsiz = n;
  root = 0;
  GetRoot(1, 0);
  Point_DC(root);
  printf("%lld\n", ans);
}
int main() {
  init();
  solve();
  return 0;
}
