#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const long long inf = 10000005;
int nsize, root, n, tot, nedge, hed[maxn], father[maxn], maxson[maxn], sz[maxn],
    vis[maxn];
long long M, pw[maxn];
map<int, int> up[maxn], cst[maxn];
vector<int> dist[maxn], down[maxn];
struct Edge {
  int todot, nex;
  long long cost;
} edge[maxn << 1];
inline int read() {
  int x = 0;
  int w = 0;
  char ch = 0;
  while (ch < '0' || ch > '9') w |= ch == '-', ch = getchar();
  while (ch >= '0' && ch <= '9')
    x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return w ? -x : x;
}
void addedge(int a, int b, long long c) {
  edge[nedge].todot = b;
  edge[nedge].nex = hed[a];
  edge[nedge].cost = c;
  hed[a] = nedge++;
}
void getsize(int k, int fa) {
  ++nsize;
  for (int i = hed[k]; i != -1; i = edge[i].nex) {
    int v = edge[i].todot;
    if ((v == fa) || (vis[v])) continue;
    getsize(v, k);
  }
}
void getroot(int k, int fa) {
  maxson[k] = 0;
  sz[k] = 1;
  for (int i = hed[k]; i != -1; i = edge[i].nex) {
    int v = edge[i].todot;
    if ((v == fa) || (vis[v])) continue;
    getroot(v, k);
    sz[k] += sz[v];
    maxson[k] = max(maxson[k], sz[v]);
  }
  maxson[k] = max(maxson[k], nsize - sz[k]);
  if (maxson[k] < maxson[root]) root = k;
}
void ex_gcd(long long a, long long b, long long c, long long &x, long long &y) {
  if (!b) {
    x = c / a;
    y = 0;
    return;
  }
  if (!(a % b)) {
    x = 0;
    y = c / b;
    return;
  }
  ex_gcd(b, a % b, c, y, x);
  y -= (a / b) * x;
}
void Merge(int k, int fa, int gf, int f, int dis, long long nowdown) {
  for (int i = hed[k]; i != -1; i = edge[i].nex) {
    int v = edge[i].todot;
    if ((vis[v]) || (v == fa)) continue;
    ++tot;
    father[tot - 1] = f ? f : v;
    dist[gf].push_back(dis + 1);
    down[gf].push_back((nowdown * 10 + edge[i].cost) % M);
    if (!f)
      Merge(v, k, gf, v, dis + 1, (nowdown * 10 + edge[i].cost) % M);
    else
      Merge(v, k, gf, f, dis + 1, (nowdown * 10 + edge[i].cost) % M);
  }
}
void getup(int k, int fa, int gf, long long nowup, int dis) {
  for (int i = hed[k]; i != -1; i = edge[i].nex) {
    int v = edge[i].todot;
    if ((vis[v]) || (v == fa)) continue;
    up[gf][(pw[dis] * edge[i].cost + nowup) % M]++;
    getup(v, k, gf, (pw[dis] * edge[i].cost + nowup) % M, dis + 1);
  }
}
long long calc(int k) {
  int t = dist[k].size();
  long long ret = 0;
  for (int i = 0; i <= t - 1; i++) {
    long long x, y;
    ex_gcd(M, pw[dist[k][i]], 1, x, y);
    y = ((y % M) + M) % M;
    y = (y * (-down[k][i]) % M + M) % M;
    long long tx, ty;
    ex_gcd(M, 10 % M, 1, tx, ty);
    ty = ((ty % M) + M) % M;
    ty = (((y - cst[k][father[i]]) * ty) % M + M) % M;
    ret += up[k][y] - up[father[i]][ty] - (cst[k][father[i]] % M == y);
    if (!down[k][i]) ret++;
  }
  ret += up[k][0];
  up[k].clear();
  dist[k].clear();
  down[k].clear();
  for (int i = hed[k]; i != -1; i = edge[i].nex) {
    int v = edge[i].todot;
    if (vis[v]) continue;
    dist[v].clear();
    up[v].clear();
    down[v].clear();
  }
  return ret;
}
long long getans(int k) {
  vis[k] = 1;
  tot = 0;
  dist[k].clear();
  down[k].clear();
  Merge(k, k, k, 0, 0, 0);
  up[k].clear();
  getup(k, k, k, 0, 0);
  for (int i = hed[k]; i != -1; i = edge[i].nex) {
    int v = edge[i].todot;
    if (vis[v]) continue;
    up[v].clear();
    getup(v, k, v, 0, 0);
  }
  long long ret = calc(k);
  for (int i = hed[k]; i != -1; i = edge[i].nex) {
    int v = edge[i].todot;
    if (vis[v]) continue;
    nsize = 0;
    getsize(v, k);
    root = 0;
    getroot(v, k);
    ret += getans(root);
  }
  return ret;
}
int main() {
  n = read();
  M = read();
  pw[0] = 1 % M;
  for (int i = 1; i <= n; i++) pw[i] = (pw[i - 1] * 10) % M;
  nedge = 0;
  memset(hed, -1, sizeof(hed));
  for (int i = 1; i <= n - 1; i++) {
    int a, b;
    long long c;
    a = read();
    b = read();
    c = read();
    ++a;
    ++b;
    addedge(a, b, c);
    addedge(b, a, c);
    cst[a][b] = cst[b][a] = c;
  }
  maxson[0] = inf;
  root = 0;
  nsize = n;
  getroot(1, 1);
  long long ans = getans(root);
  printf("%I64d\n", ans);
  return 0;
}
