#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T, class T1>
inline void gn(T &first, T1 &second) {
  gn(first);
  gn(second);
}
template <class T, class T1, class T2>
inline void gn(T &first, T1 &second, T2 &z) {
  gn(first);
  gn(second);
  gn(z);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
template <class T, class U>
inline void print(T first, U second) {
  printsp(first);
  println(second);
}
template <class T, class U, class V>
inline void print(T first, U second, V z) {
  printsp(first);
  printsp(second);
  println(z);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
vector<int> adj[101010];
int nn, qf, qb, q[101010], sz[101010], fa[101010], vst[101010];
int M, vis[101010];
int find_root(int u) {
  qf = qb = 0;
  q[qb++] = u;
  fa[u] = 0;
  while (qf < qb) {
    u = q[qf++];
    for (int i = adj[u].size(); i--;) {
      int v = adj[u][i];
      if (v == fa[u] || vst[v]) continue;
      fa[v] = u;
      q[qb++] = v;
    }
  }
  nn = qb;
  for (int i = nn; i--;) {
    sz[u = q[i]] = 1;
    int mx = 0;
    for (int j = adj[u].size(); j--;) {
      int v = adj[u][j];
      if (v == fa[u] || vst[v]) continue;
      smax(mx, sz[v]);
      sz[u] += sz[v];
    }
    if (mx * 2 <= nn && sz[u] * 2 >= nn) return u;
  }
}
int inv[101010];
vector<int> wei[101010], tmp[101010];
long long ans = 0;
int head[1000100], nxt[1000100], val[1000100], cnt[1000100];
int E, R = 701010;
int get_cnt(int t) {
  int u = t % R;
  for (int e = head[u]; ~e; e = nxt[e]) {
    if (val[e] == t) return cnt[e];
  }
  return 0;
}
int history[101010], h = 0;
void update(int t) {
  int u = t % R;
  for (int e = head[u]; ~e; e = nxt[e]) {
    if (val[e] == t) {
      cnt[e]++;
      return;
    }
  }
  history[h++] = u;
  cnt[E] = 1;
  val[E] = t;
  nxt[E] = head[u];
  head[u] = E++;
}
void clear_data() {
  for (int i = 0; i < h; i++) head[history[i]] = -1;
  E = h = 0;
}
int flag, num[101010], num1[101010], dis[101010], pw[101010];
void dfs(int u, int fa = 0) {
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == fa || vst[v]) continue;
    qf = qb = 0;
    ++flag;
    q[qb++] = v;
    vis[v] = flag;
    num[v] = wei[u][i] % M;
    num1[v] = wei[u][i] % M;
    dis[v] = 1;
    while (qf < qb) {
      int uu = q[qf++];
      ans += (num[uu] == 0) + (num1[uu] == 0);
      for (int j = 0; j < adj[uu].size(); j++) {
        int vv = adj[uu][j];
        if (vv == u || vis[vv] == flag || vst[vv]) continue;
        vis[vv] = flag;
        num[vv] = (num[uu] + (long long)pw[dis[uu]] * wei[uu][j]) % M;
        num1[vv] = (num1[uu] * 10LL + wei[uu][j]) % M;
        dis[vv] = dis[uu] + 1;
        q[qb++] = vv;
      }
    }
    tmp[v].resize(qb);
    for (int j = 0; j < qb; j++) tmp[v][j] = q[j];
  }
  for (int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == fa || vst[v]) continue;
    for (int j = 0; j < tmp[v].size(); j++) {
      int uu = tmp[v][j];
      ans += get_cnt((long long)(M - num1[uu]) * inv[dis[uu]] % M);
    }
    for (int j = 0; j < tmp[v].size(); j++) {
      int uu = tmp[v][j];
      update(num[uu]);
    }
  }
  clear_data();
  for (int i = adj[u].size(); i--;) {
    int v = adj[u][i];
    if (v == fa || vst[v]) continue;
    for (int j = 0; j < tmp[v].size(); j++) {
      int uu = tmp[v][j];
      ans += get_cnt((long long)(M - num1[uu]) * inv[dis[uu]] % M);
    }
    for (int j = 0; j < tmp[v].size(); j++) {
      int uu = tmp[v][j];
      update(num[uu]);
    }
  }
  clear_data();
  for (int i = 0; i < adj[u].size(); i++) tmp[adj[u][i]].clear();
}
void solve(int u) {
  u = find_root(u);
  dfs(u);
  vst[u] = 1;
  for (int i = adj[u].size(); i--;) {
    int v = adj[u][i];
    if (!vst[v]) solve(v);
  }
}
int main() {
  int n;
  gn(n, M);
  memset(head, -1, sizeof head);
  for (int i = 1; i < n; i++) {
    int u, v, c;
    gn(u, v, c);
    u++;
    v++;
    adj[u].push_back(v);
    adj[v].push_back(u);
    wei[u].push_back(c);
    wei[v].push_back(c);
  }
  if (M == 1) {
    println((long long)n * (n - 1));
    return 0;
  }
  int m = M, mod = M;
  for (int i = 2; i * i <= m; i++)
    if (m % i == 0) {
      while (m % i == 0) m /= i;
      mod -= mod / i;
    }
  if (m > 1) mod -= mod / m;
  int c = power(10, mod - 1, M);
  assert((long long)c * 10 % M == 1);
  for (int i = inv[0] = 1; i < 101010; i++)
    inv[i] = (long long)inv[i - 1] * c % M;
  for (int i = pw[0] = 1; i < 101010; i++)
    pw[i] = (long long)pw[i - 1] * 10 % M;
  solve(1);
  println(ans);
  return 0;
}
