#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, LOG = 19, inf = 1e9;
int m;
int phi(int n) {
  int res = n;
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0) {
      while (n % i == 0) {
        n /= i;
      }
      res -= res / i;
    }
  if (n > 1) {
    res -= res / n;
  }
  return res;
}
int add(int x, int y) { return x + y >= m ? x + y - m : x + y; }
int sub(int x, int y) { return x - y < 0 ? x - y + m : x - y; }
int mul(int x, int y) { return 1ll * x * y % m; }
int deg(int x, int y) {
  int res = 1;
  for (int z = x; y; y >>= 1, z = mul(z, z))
    if (y & 1) res = mul(res, z);
  return res;
}
int deg10[N], rev10[N];
int n;
vector<pair<int, int>> g[N];
int from[N], h[N];
int dist_down[N], dist_up[N];
pair<int, int> subtree[N];
vector<int> order;
void dfs_precalc(int v) {
  subtree[v].first = (int)order.size();
  order.emplace_back(v);
  for (auto &e : g[v]) {
    int u = e.first, w = e.second;
    if (u != from[v]) {
      from[u] = v;
      h[u] = h[v] + 1;
      dist_up[u] = add(dist_up[v], mul(w, deg10[h[u] - 1]));
      dist_down[u] = add(mul(dist_down[v], 10), w);
      dfs_precalc(u);
      order.emplace_back(v);
    }
  }
  subtree[v].second = (int)order.size() - 1;
}
int lenfor[N * 2];
pair<int, int> sp_lca[LOG][N * 2];
void build_lca() {
  int k = (int)order.size();
  for (int i = 2; i <= k; ++i) {
    lenfor[i] = lenfor[i >> 1] + 1;
  }
  for (int i = 0; i < LOG; ++i) {
    for (int j = 0; j < k; ++j) {
      sp_lca[i][j] = make_pair(inf, inf);
    }
  }
  for (int i = 0; i < LOG; ++i) {
    for (int j = 0; j + (1 << i) - 1 < k; ++j) {
      if (i == 0) {
        sp_lca[i][j] = make_pair(h[order[j]], order[j]);
      } else {
        sp_lca[i][j] = min(sp_lca[i - 1][j], sp_lca[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
}
int get_lca(int v, int u) {
  int L = subtree[v].first, R = subtree[u].first;
  if (L > R) {
    swap(L, R);
  }
  int len = lenfor[R - L + 1];
  return min(sp_lca[len][L], sp_lca[len][R - (1 << len) + 1]).second;
}
int get_up(int v, int u) {
  return mul(sub(dist_up[v], dist_up[u]), rev10[h[u]]);
}
int get_down(int v, int u) {
  return sub(dist_down[u], mul(dist_down[v], deg10[h[u] - h[v]]));
}
int get_dist(int v, int u) {
  int lca = get_lca(v, u);
  if (v == lca) {
    return get_down(v, u);
  }
  if (u == lca) {
    return get_up(v, u);
  }
  return add(mul(get_up(v, lca), deg10[h[u] - h[lca]]), get_down(lca, u));
}
int get_len(int v, int u) {
  int lca = get_lca(v, u);
  return h[v] + h[u] - 2 * h[lca];
}
int sz[N];
bool used[N];
void dfs_size(int v, int p) {
  sz[v] = 1;
  for (auto &e : g[v]) {
    int u = e.first, w = e.second;
    if (!used[u] && u != p) {
      dfs_size(u, v);
      sz[v] += sz[u];
    }
  }
}
int dfs_centroid(int v, int p, int s) {
  for (auto &e : g[v]) {
    int u = e.first, w = e.second;
    if (!used[u] && u != p && sz[u] * 2 > s) {
      return dfs_centroid(u, v, s);
    }
  }
  return v;
}
vector<int> control[N];
long long ans = 0;
long long get(vector<int> &a, vector<pair<int, int>> &b) {
  unordered_map<int, int> cnt;
  for (int i = 0; i < (int)b.size(); ++i) {
    ++cnt[mul(sub(0, b[i].first), rev10[b[i].second])];
  }
  long long res = 0;
  for (int i = 0; i < (int)a.size(); ++i) {
    --cnt[mul(sub(0, b[i].first), rev10[b[i].second])];
    res += cnt[a[i]];
    ++cnt[mul(sub(0, b[i].first), rev10[b[i].second])];
  }
  return res;
}
int find_centroid(int v) {
  dfs_size(v, 0);
  int centroid = dfs_centroid(v, 0, sz[v]);
  used[centroid] = true;
  vector<int> global_a;
  vector<pair<int, int>> global_b;
  global_a.emplace_back(0);
  global_b.emplace_back(0, 0);
  control[centroid].emplace_back(centroid);
  for (auto &e : g[centroid]) {
    int u = e.first, w = e.second;
    if (!used[u]) {
      int nxt_centroid = find_centroid(u);
      vector<int> curr_a;
      vector<pair<int, int>> curr_b;
      for (int &x : control[nxt_centroid]) {
        curr_a.emplace_back(get_dist(x, centroid));
        global_a.emplace_back(get_dist(x, centroid));
        curr_b.emplace_back(get_dist(centroid, x), get_len(centroid, x));
        global_b.emplace_back(get_dist(centroid, x), get_len(centroid, x));
        control[centroid].emplace_back(x);
      }
      ans -= get(curr_a, curr_b);
    }
  }
  ans += get(global_a, global_b);
  return centroid;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  if (m == 1) {
    cout << 1ll * n * n - n << "\n";
    return 0;
  }
  deg10[0] = 1;
  rev10[0] = 1;
  rev10[1] = deg(10, phi(m) - 1);
  for (int i = 1; i <= n; ++i) {
    deg10[i] = mul(deg10[i - 1], 10);
    if (i > 1) {
      rev10[i] = mul(rev10[i - 1], rev10[1]);
    }
  }
  for (int i = 1; i < n; ++i) {
    int v, u, w;
    cin >> v >> u >> w;
    ++v, ++u;
    w %= m;
    g[v].emplace_back(u, w);
    g[u].emplace_back(v, w);
  }
  dfs_precalc(1);
  build_lca();
  find_centroid(1);
  cout << ans << "\n";
  return 0;
}
