#include <bits/stdc++.h>
using namespace std;
set<pair<long long, long long>> adj[100005];
long long msb[100005], lsb[100005];
long long mod, root;
long long par[25][100005], depth[100005], sub[100005], p[100005], n, pw[100005],
    pre_inv[100005];
vector<pair<long long, long long>> vec[100005];
unordered_map<long long, long long> m[100005];
vector<long long> ctree[100005];
long long pow1(long long a, long long b) {
  long long x = 1, y = a;
  while (b > 0) {
    if (b % 2 == 1) {
      x = (x * y);
      if (x > mod) x %= mod;
    }
    y = (y * y);
    if (y > mod) y %= mod;
    b /= 2;
  }
  return x % mod;
}
long long modInverse(long long a, long long m) {
  long long m0 = m;
  long long y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
void addedge(long long u, long long v, long long wt) {
  adj[u].insert({v, wt});
  adj[v].insert({u, wt});
}
void dfs1(long long u, long long parent, long long level) {
  par[0][u] = parent;
  depth[u] = level;
  for (auto k : adj[u]) {
    if (k.first == parent) continue;
    msb[k.first] = (((k.second * pw[level]) % mod) + msb[u]) % mod;
    lsb[k.first] = ((k.second + (10 * lsb[u]) % mod)) % mod;
    dfs1(k.first, u, level + 1);
  }
}
void preprocess() {
  pw[0] = 1;
  for (int i = 1; i < 100005; i++) pw[i] = (pw[i - 1] * 10) % mod;
  for (int i = 0; i < 100005; i++) pre_inv[i] = modInverse(pw[i], mod);
  dfs1(0, -1, 0);
  for (long long d = 1; d <= 23; d++)
    for (long long i = 0; i < n; i++) {
      long long mid = par[d - 1][i];
      if (mid != -1) par[d][i] = par[d - 1][mid];
    }
}
long long walk(long long i, long long k) {
  for (long long d = 0; d <= 23; d++) {
    if ((k & 1 << d) > 0) i = par[d][i];
  }
  return i;
}
long long lca(long long i, long long j) {
  if (depth[i] > depth[j]) i = walk(i, depth[i] - depth[j]);
  if (depth[i] < depth[j]) j = walk(j, depth[j] - depth[i]);
  if (i == j) return i;
  for (long long d = 23; d >= 0; d--) {
    if (par[d][i] != par[d][j]) {
      i = par[d][i];
      j = par[d][j];
    }
  }
  return par[0][i];
}
long long dist(long long i, long long j) {
  return depth[i] + depth[j] - 2 * depth[lca(i, j)];
}
long long scale(long long i, long long factor) {
  if (factor >= 0)
    return (i * pw[factor]) % mod;
  else
    return (i * (pre_inv[abs(factor)]) % mod) % mod;
}
long long modval(long long i, long long j) {
  long long l1 = lca(i, j);
  long long t1 = msb[l1];
  long long req = depth[j] - depth[l1];
  long long have = depth[l1];
  long long a1 = (scale(msb[i] - t1, req - have) + mod) % mod;
  long long a2 = (lsb[j] - ((lsb[l1] * pw[req] % mod) + mod) % mod) % mod;
  return (a1 + a2 + mod) % mod;
}
long long nn = 0;
void getsub(long long u, long long par) {
  sub[u] = 1;
  nn++;
  for (auto k : adj[u]) {
    if (k.first == par) continue;
    getsub(k.first, u);
    sub[u] += sub[k.first];
  }
}
long long getcentroid(long long u, long long par) {
  for (auto k : adj[u]) {
    if (k.first == par) continue;
    if (sub[k.first] > nn / 2) return getcentroid(k.first, u);
  }
  return u;
}
void decompose(long long u, long long parent) {
  nn = 0;
  getsub(u, -1);
  long long centroid = getcentroid(u, parent);
  if (parent != -1) {
    ctree[parent].push_back(centroid);
  } else
    root = centroid;
  p[centroid] = parent;
  for (auto k : adj[centroid]) {
    adj[k.first].erase({centroid, k.second});
    decompose(k.first, centroid);
  }
  adj[centroid].clear();
}
void dfs2(int i, int u, int par) {
  if (par != -1) {
    vec[i].push_back({modval(i, u), dist(i, u)});
    m[i][(modval(u, i) + mod) % mod]++;
  }
  for (auto k : ctree[u]) dfs2(i, k, u);
}
void DFS2() {
  for (int i = 0; i < n; i++) dfs2(i, i, -1);
}
long long ans = 0;
vector<pair<int, int>> temp;
void dfs4(int from, int u, int par, int keep) {
  temp.push_back({modval(from, u), dist(from, u)});
  m[from][modval(u, from)] += keep;
  for (auto k : ctree[u]) dfs4(from, k, u, keep);
}
void remove_compute_add(int i, int from) {
  temp.clear();
  dfs4(from, i, -1, -1);
  for (auto k : temp) {
    long long c1 = (mod - k.first + mod) % mod;
    long long inv = pre_inv[k.second];
    ans += m[from][(inv * c1) % mod];
  }
  temp.clear();
  dfs4(from, i, -1, 1);
}
void dfs3(long long u, long long par) {
  for (auto k : ctree[u]) {
    remove_compute_add(k, u);
    dfs3(k, u);
  }
}
int main() {
  scanf("%lld %lld", &n, &mod);
  for (long long i = 0; i < n - 1; i++) {
    long long x, y, z;
    scanf("%lld %lld %lld", &x, &y, &z);
    addedge(x, y, z);
  }
  memset(par, -1, sizeof(par));
  preprocess();
  decompose(1, -1);
  DFS2();
  long long single_count = 0;
  dfs3(root, -1);
  for (int i = 0; i < n; i++) single_count += m[i][0];
  for (long long i = 0; i < n; i++)
    for (auto k : vec[i])
      if (k.first == 0) single_count++;
  printf("%lld\n", ans + single_count);
}
