#include <bits/stdc++.h>
using namespace std;
bool chkmi(int &x, int y) { return x > y ? x = y, true : false; }
bool chkmx(int &x, int y) { return x < y ? x = y, true : false; }
int Head[100005], Nxt[100005 << 1], E[100005 << 1], Val[100005 << 1], tol;
void Edge(int x, int y, int v) {
  E[tol] = y;
  Val[tol] = v;
  Nxt[tol] = Head[x];
  Head[x] = tol++;
}
int Mod;
int H[100005];
struct node {
  int x, y;
};
node extgcd(int x, int y) {
  if (!y)
    return (node){1, 0};
  else {
    node tmp = extgcd(y, x % y);
    return (node){tmp.y, tmp.x - x / y * tmp.y};
  }
}
int Get(int x, int y) {
  return (1ll * extgcd(x, Mod).x * (-y) % Mod + Mod) % Mod;
}
int sz[100005], mx[100005], mark[100005];
int tot, Min, root;
void dfs_sz(int x, int fr) {
  sz[x] = 1;
  mx[x] = 0;
  for (int i = Head[x]; ~i; i = Nxt[i])
    if (!mark[E[i]] && E[i] != fr) {
      dfs_sz(E[i], x);
      sz[x] += sz[E[i]];
      chkmx(mx[x], sz[E[i]]);
    }
}
void dfs_rt(int x, int fr) {
  chkmx(mx[x], tot - sz[x]);
  if (chkmi(Min, mx[x])) root = x;
  for (int i = Head[x]; ~i; i = Nxt[i])
    if (!mark[E[i]] && E[i] != fr) dfs_rt(E[i], x);
}
long long res;
map<int, int> cnt[2];
int Que[2][100005];
int top1, top2;
void DFS(int x, int fr, int num1, int num2, int len) {
  if (!num1) res++;
  if (!num2) res++;
  int tmp = Get(H[len], num2);
  res += cnt[0][num1];
  res += cnt[1][tmp];
  Que[0][++top1] = tmp;
  Que[1][++top2] = num1;
  for (int i = Head[x]; ~i; i = Nxt[i])
    if (!mark[E[i]] && E[i] != fr) {
      DFS(E[i], x, (num1 + (long long)Val[i] * H[len]) % Mod,
          ((long long)num2 * 10 + Val[i]) % Mod, len + 1);
    }
}
void solve(int x) {
  cnt[0].clear();
  cnt[1].clear();
  for (int i = Head[x]; ~i; i = Nxt[i]) {
    if (mark[E[i]]) continue;
    top1 = top2 = 0;
    DFS(E[i], x, Val[i] % Mod, Val[i] % Mod, 1);
    for (int i = (1), _t = (top1); i <= _t; ++i) cnt[0][Que[0][i]]++;
    for (int i = (1), _t = (top2); i <= _t; ++i) cnt[1][Que[1][i]]++;
  }
}
void dfs(int x) {
  dfs_sz(x, 0);
  Min = 0x3f3f3f3f;
  tot = sz[x];
  dfs_rt(x, 0);
  x = root;
  mark[x] = 1;
  solve(x);
  for (int i = Head[x]; ~i; i = Nxt[i])
    if (!mark[E[i]]) dfs(E[i]);
}
int main() {
  memset(Head, -1, sizeof(Head));
  int n;
  scanf("%d%d", &n, &Mod);
  H[0] = 1 % Mod;
  for (int i = (1), _t = (n); i <= _t; ++i)
    H[i] = (long long)H[i - 1] * 10 % Mod;
  for (int i = (2), _t = (n); i <= _t; ++i) {
    int x, y, v;
    scanf("%d%d%d", &x, &y, &v);
    x++;
    y++;
    Edge(x, y, v);
    Edge(y, x, v);
  }
  dfs(1);
  printf("%lld\n", res);
  return 0;
}
