#include <bits/stdc++.h>
using namespace std;
long long mod = 0;
const int N = 100005;
vector<array<int, 2>> v[N];
vector<set<int>> g(N);
vector<int> depth(N, 0);
vector<vector<int>> p(N, vector<int>(17, 0));
vector<long long> up(N, 0);
vector<long long> down(N, 0);
vector<int> sz(N, 0);
vector<int> ch[N];
vector<int> st[N];
vector<long long> pw(N, 1);
vector<long long> inv(N, 1);
long long res = 0;
int root = 0;
void dfs(int a) {
  depth[a] = depth[p[a][0]] + 1;
  for (int i = 1; i < 17; i++) p[a][i] = p[p[a][i - 1]][i - 1];
  for (auto [to, k] : v[a]) {
    if (to == p[a][0]) continue;
    p[to][0] = a;
    down[to] = (10 * down[a] + k) % mod;
    up[to] = (pw[depth[a] - 1] * k + up[a]) % mod;
    dfs(to);
  }
}
int lca(int a, int b) {
  if (depth[a] > depth[b]) swap(a, b);
  for (int i = 16; i >= 0; i--)
    if (depth[p[b][i]] >= depth[a]) b = p[b][i];
  if (a == b) return a;
  for (int i = 16; i >= 0; i--) {
    if (p[a][i] != p[b][i]) {
      a = p[a][i];
      b = p[b][i];
    }
  }
  return p[a][0];
}
int dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }
long long h(int a, int b) {
  int l = lca(a, b);
  long long x = (((up[a] - up[l] + mod) % mod) * inv[depth[l] - 1]) % mod;
  long long y =
      (((down[b] - pw[depth[b] - depth[l]] * down[l]) % mod) + mod) % mod;
  long long z = (pw[depth[b] - depth[l]] * x + y) % mod;
  return z;
}
void find_sz(int a, int par = 0) {
  sz[a] = 1;
  for (int to : g[a]) {
    if (to == par) continue;
    find_sz(to, a);
    sz[a] += sz[to];
  }
}
int find_centroid(int a, int par, int n) {
  for (int to : g[a]) {
    if (to == par) continue;
    if (sz[to] > n / 2) return find_centroid(to, a, n);
  }
  return a;
}
void build_cd(int a, int par = 0) {
  find_sz(a);
  int n = sz[a];
  int centroid = find_centroid(a, 0, n);
  if (par == 0) root = centroid;
  ch[par].push_back(centroid);
  for (int to : g[centroid]) {
    g[to].erase(centroid);
    build_cd(to, centroid);
  }
}
long long fpow(long long b, long long e) {
  long long x = 1;
  while (e) {
    if (e & 1) x = (x * b) % mod;
    b = (b * b) % mod;
    e /= 2;
  }
  return x;
}
long long find_inv() {
  long long x = mod;
  long long tmp = mod;
  for (long long i = 2; i * i <= tmp; i++) {
    if ((tmp % i) == 0) {
      x /= i;
      x *= (i - 1);
    }
    while ((tmp % i) == 0) tmp /= i;
  }
  if (tmp > 1) {
    x /= tmp;
    x *= (tmp - 1);
  }
  return fpow(10, x - 1);
}
void solve(int a) {
  map<int, int> m;
  for (int to : ch[a]) {
    solve(to);
    for (int x : st[to]) {
      m[h(x, a)]++;
      st[a].push_back(x);
    }
  }
  res += m[0];
  st[a].push_back(a);
  for (int to : ch[a]) {
    for (int x : st[to]) m[h(x, a)]--;
    for (int x : st[to]) {
      long long z = h(a, x);
      if (z == 0) res++;
      long long val = (((-z * inv[dist(a, x)]) % mod) + mod) % mod;
      res += m[val];
    }
    for (int x : st[to]) m[h(x, a)]++;
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n >> mod;
  for (int i = 0; i < n - 1; i++) {
    int a, b, k;
    cin >> a >> b >> k;
    a++;
    b++;
    v[a].push_back({b, k});
    v[b].push_back({a, k});
    g[a].insert(b);
    g[b].insert(a);
  }
  for (int i = 1; i <= n; i++) pw[i] = (10 * pw[i - 1]) % mod;
  inv[1] = find_inv();
  for (int i = 2; i <= n; i++) inv[i] = (inv[i - 1] * inv[1]) % mod;
  dfs(1);
  build_cd(1);
  solve(root);
  cout << res << "\n";
  return 0;
}
