#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 20;
const int INF = 1e9;
struct Edge {
  int to, next, w;
} e[2 * N];
int n, head[N], M, num;
map<int, int> mp, sp;
long long ans;
void add(int u, int v, int w) {
  e[num].next = head[u];
  e[num].to = v, e[num].w = w;
  head[u] = num++;
}
bool ban[N];
int sz[N], f[N];
int root, siz;
void get_root(int u, int fa) {
  sz[u] = 1, f[u] = 0;
  for (int i = head[u]; i != -1; i = e[i].next) {
    int v = e[i].to;
    if (v == fa || ban[v]) continue;
    get_root(v, u);
    sz[u] += sz[v];
    f[u] = max(sz[v], f[u]);
  }
  f[u] = max(f[u], siz - sz[u]);
  if (f[u] < f[root]) root = u;
}
int dis[N], seq[N], tol, pos[N];
long long inv[N], path[N], ten[N], gao[N];
void dfs(int u, int fa) {
  pos[u] = tol;
  seq[tol++] = u;
  sz[u] = 1;
  for (int i = head[u]; i != -1; i = e[i].next) {
    int v = e[i].to;
    if (v == fa || ban[v]) continue;
    dis[v] = dis[u] + 1;
    path[v] = ((1LL * path[u]) * 10 + e[i].w) % M;
    gao[v] = (gao[u] + ten[dis[v] - 1] * e[i].w) % M;
    if (gao[v] == 0) ans++;
    if (path[v] == 0) ans++;
    dfs(v, u);
    sz[u] += sz[v];
  }
}
void sovle(int u, int ssz) {
  root = 0, siz = ssz, f[0] = INF;
  get_root(u, 0);
  int rt = root;
  dis[rt] = 0, path[rt] = 0, tol = 0;
  gao[rt] = 0;
  long long pre = ans;
  dfs(rt, 0);
  mp.clear(), sp.clear();
  for (int i = head[rt]; i != -1; i = e[i].next) {
    int v = e[i].to;
    if (ban[v]) continue;
    for (int j = pos[v]; j < pos[v] + sz[v]; j++) {
      int u = seq[j];
      int tmp = ((M - path[u]) * inv[dis[u]]) % M;
      ans += mp[tmp] + sp[gao[u]];
    }
    for (int j = pos[v]; j < pos[v] + sz[v]; j++) {
      int u = seq[j];
      int tmp = ((M - path[u]) * inv[dis[u]]) % M;
      mp[gao[u]]++, sp[tmp]++;
    }
  }
  ban[rt] = true;
  for (int i = head[rt]; i != -1; i = e[i].next) {
    int v = e[i].to;
    if (ban[v]) continue;
    sovle(v, sz[v]);
  }
}
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    long long gcd = extend_gcd(b, a % b, x, y);
    long long t = x;
    x = y;
    y = t - a / b * x;
    return gcd;
  }
}
void init() {
  memset(head, -1, sizeof(head));
  memset(ban, 0, sizeof(ban));
  num = 0;
  inv[0] = 1, ten[0] = 1;
  long long x, y;
  extend_gcd(10, M, x, y);
  x = (x % M + M) % M;
  for (int i = 1; i <= n; i++) {
    inv[i] = (inv[i - 1] * x) % M;
    ten[i] = (ten[i - 1] * 10) % M;
  }
}
int main() {
  while (scanf("%d%d", &n, &M) != EOF) {
    init();
    for (int i = 0; i < n - 1; i++) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      u++, v++;
      add(u, v, w);
      add(v, u, w);
    }
    ans = 0;
    sovle(1, n);
    printf("%I64d\n", ans);
  }
  return 0;
}
