#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXE = 200005;
struct Edge {
  int v, c, n;
  Edge() {}
  Edge(int v, int c, int n) : v(v), c(c), n(n) {}
};
struct Node {
  int v1, v2, d;
  Node() {}
  Node(int v1, int v2, int d) : v1(v1), v2(v2), d(d) {}
};
Edge E[MAXE];
int H[MAXN], cntE;
int vis[MAXN], siz[MAXN], pre[MAXN];
int Q[MAXN], head, tail;
map<int, int> mp;
Node S[MAXN];
int n, top, mod;
long long ans, p[MAXN], vp[MAXN];
void init() {
  cntE = 0;
  memset(vis, 0, sizeof vis);
  memset(H, -1, sizeof H);
}
void addedge(int u, int v, int c) {
  E[cntE] = Edge(v, c, H[u]);
  H[u] = cntE++;
}
int get_root(int s) {
  head = tail = 0;
  pre[s] = 0;
  Q[tail++] = s;
  while (head != tail) {
    int u = Q[head++];
    for (int i = H[u]; ~i; i = E[i].n) {
      int v = E[i].v;
      if (vis[v] || v == pre[u]) continue;
      pre[v] = u;
      Q[tail++] = v;
    }
  }
  int root = s, root_siz = n;
  while (head) {
    int u = Q[--head], cnt = 0;
    siz[u] = 1;
    for (int i = H[u]; ~i; i = E[i].n) {
      int v = E[i].v;
      if (vis[v] || v == pre[u]) continue;
      siz[u] += siz[v];
      if (cnt < siz[v]) cnt = siz[v];
    }
    cnt = max(cnt, tail - siz[u]);
    if (cnt < root_siz) {
      root_siz = cnt;
      root = u;
    }
  }
  return root;
}
void get_tree(int u, int f, int val1, int val2, int dep) {
  S[top++] = Node(val1, val2, dep);
  for (int i = H[u]; ~i; i = E[i].n) {
    int v = E[i].v;
    if (vis[v] || v == f) continue;
    int v1 = (1LL * val1 * 10 + E[i].c) % mod;
    int v2 = (val2 + p[dep] * E[i].c) % mod;
    get_tree(v, u, v1, v2, dep + 1);
  }
}
void dfs(int u) {
  int root = get_root(u);
  vis[root] = 1;
  mp.clear();
  vector<pair<int, int> > G;
  G.clear();
  for (int i = H[root]; ~i; i = E[i].n) {
    int v = E[i].v;
    G.push_back(pair<int, int>(v, E[i].c));
    if (vis[v]) continue;
    top = 0;
    get_tree(v, root, E[i].c % mod, E[i].c % mod, 1);
    for (int j = 0; j < top; ++j) {
      int x = (mod - S[j].v1) * vp[S[j].d] % mod;
      ans += mp[x];
    }
    for (int j = 0; j < top; ++j) {
      mp[S[j].v2]++;
      if (!S[j].v1) ans++;
      if (!S[j].v2) ans++;
    }
  }
  mp.clear();
  for (int i = G.size() - 1; ~i; --i) {
    int v = G[i].first;
    if (vis[v]) continue;
    top = 0;
    get_tree(v, root, G[i].second % mod, G[i].second % mod, 1);
    for (int j = 0; j < top; ++j) {
      int x = (mod - S[j].v1) * vp[S[j].d] % mod;
      ans += mp[x];
    }
    for (int j = 0; j < top; ++j) {
      mp[S[j].v2]++;
    }
  }
  for (int i = H[root]; ~i; i = E[i].n) {
    int v = E[i].v;
    if (!vis[v]) dfs(v);
  }
}
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0 && b == 0) return -1;
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extend_gcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
long long inv(long long a, long long n) {
  long long x, y;
  long long d = extend_gcd(a, n, x, y);
  if (d == 1)
    return (x % n + n) % n;
  else
    return -1;
}
void solve() {
  int u, v, c;
  init();
  ans = 0;
  p[0] = vp[0] = 1 % mod;
  int tmp = inv(10, mod);
  for (int i = 1; i <= n; ++i) {
    p[i] = p[i - 1] * 10 % mod;
    vp[i] = vp[i - 1] * tmp % mod;
  }
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%d", &u, &v, &c);
    ++u;
    ++v;
    addedge(u, v, c);
    addedge(v, u, c);
  }
  dfs(1);
  printf("%lld\n", ans);
}
int main() {
  while (~scanf("%d%d", &n, &mod)) solve();
  return 0;
}
