#include <bits/stdc++.h>
using namespace std;
long long gcdex(long long a, long long b, long long& x, long long& y,
                long long qax = 1, long long qay = 0, long long qbx = 0,
                long long qby = 0) {
  if (b == 0) {
    x = qax;
    y = qay;
    return a;
  }
  long long q = a / b;
  return gcdex(b, a % b, x, y, qbx, qby, qax - q * qbx, qay - q * qby);
}
long long inv(long long a, long long m) {
  long long x, y;
  assert(gcdex(a, m, x, y) == 1);
  return ((x % m) + m) % m;
}
const int N = 100010;
vector<pair<int, int>> adj[N];
int size[N], mark[N], bc[N];
vector<int> dist[N], s1[N], s2[N];
;
int dfs(int u, int p = -1) {
  size[u] = 1;
  bc[u] = 0;
  for (auto& e : adj[u]) {
    int v = e.first;
    if (v == p || mark[v]) continue;
    size[u] += dfs(v, u);
    if (!bc[u] || size[v] > size[bc[u]]) bc[u] = v;
  }
  return size[u];
}
int M;
int pot[N];
void prep(int u, int p = -1, int d = 0, int e1 = 0, int e2 = 0) {
  dist[u].push_back(d);
  s1[u].push_back(e1);
  s2[u].push_back(e2);
  for (auto& e : adj[u]) {
    int v = e.first;
    if (v == p || mark[v]) continue;
    prep(v, u, d + 1, (10ll * e1 + e.second) % M,
         (1ll * pot[d] * e.second + e2) % M);
  }
}
unordered_map<int, int> mais[N], menos[N];
int pr[N];
int decomp(int u) {
  dfs(u);
  int c = u;
  while (bc[c] && 2 * size[bc[c]] > size[u]) c = bc[c];
  mark[c] = 1;
  prep(c);
  for (auto& e : adj[c]) {
    int v = e.first;
    if (mark[v]) continue;
    pr[decomp(v)] = c;
  }
  return c;
}
void add(int u, int dt) {
  for (int i = 0, x = u, last = 0; i < dist[u].size(); i++, x = pr[last = x]) {
    mais[x][s2[u][i]] += dt;
    if (last) menos[last][s2[u][i]] += dt;
  }
}
int inv_pot[N];
int query(int u) {
  int res = 0;
  for (int i = 0, x = u, last = 0; i < dist[u].size(); i++, x = pr[last = x]) {
    int a = M - s1[u][i];
    int b = (1ll * inv_pot[dist[u][i]] * a) % M;
    res += mais[x][b];
    if (last) res -= menos[last][b];
  }
  return res;
}
int main() {
  int n;
  scanf("%d%d", &n, &M);
  pot[0] = inv_pot[0] = 1;
  for (int i = 1; i < n; i++) {
    pot[i] = (10ll * pot[i - 1]) % M;
    inv_pot[i] = inv(pot[i], M);
  }
  for (int i = 1; i < n; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u++, v++;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  decomp(1);
  for (int i = 1; i <= n; i++) {
    reverse(begin(dist[i]), end(dist[i]));
    reverse(begin(s1[i]), end(s1[i]));
    reverse(begin(s2[i]), end(s2[i]));
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += query(i);
    add(i, 1);
  }
  for (int i = 1; i <= n; i++) add(i, -1);
  for (int i = n; i >= 1; i--) {
    ans += query(i);
    add(i, 1);
  }
  printf("%lld\n", ans);
  return 0;
}
