#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5 + 5;
vector<pair<int, int> > graph[mx];
int MOD, n, PHI;
long long bigmod(long long x, long long n) {
  long long res = 1;
  while (n > 0) {
    if (n % 2) res = (res * x) % MOD;
    n /= 2;
    x = (x * x) % MOD;
  }
  return res;
}
long long inv(int n) { return bigmod(n, PHI - 1); }
bool flag[mx];
vector<int> primes;
void sieve() {
  primes.push_back(2);
  for (int i = 3; i < mx; i += 2)
    if (!flag[i]) {
      primes.push_back(i);
      for (long long j = (long long)i * i; j < mx; j += i) flag[j] = true;
    }
}
int phi(int n) {
  long long num = 1;
  long long num2 = n;
  for (long long i = 0; primes[i] * primes[i] <= n; i++) {
    if (n % primes[i] == 0) {
      num2 /= primes[i];
      num *= (primes[i] - 1);
    }
    while (n % primes[i] == 0) {
      n /= primes[i];
    }
  }
  if (n > 1) {
    num2 /= n;
    num *= (n - 1);
  }
  n = 1;
  num *= num2;
  return num;
}
vector<int> nodes;
int treesize, sz[mx];
bool vis[mx];
void dfs(int u, int par) {
  if (par == -1) nodes.clear();
  sz[u] = 1;
  nodes.push_back(u);
  for (int i = 0; i < graph[u].size(); i++) {
    int v = graph[u][i].first;
    if (vis[v]) continue;
    if (v == par) continue;
    dfs(v, u);
    sz[u] += sz[v];
  }
  if (par == -1) treesize = sz[u];
}
int findCent(int u, int par) {
  for (int i = 0; i < graph[u].size(); i++) {
    int v = graph[u][i].first;
    if (vis[v]) continue;
    if (v == par) continue;
    if (sz[v] * 2 > treesize) return findCent(v, u);
  }
  return u;
}
long long mult(long long a, long long b) { return (a * b) % MOD; }
long long add(long long a, long long b) { return (a + b + MOD) % MOD; }
int parts = 0, dppart[mx], hi[mx];
long long down[mx], up[mx];
void prep(int u, int p, int cent) {
  if (p == cent) {
    dppart[u] = parts;
    parts++;
  } else if (p != -1) {
    dppart[u] = dppart[p];
  }
  for (int i = 0; i < graph[u].size(); i++) {
    int v = graph[u][i].first;
    int w = graph[u][i].second;
    if (v == p || vis[v]) continue;
    down[v] = add(mult(down[u], 10), w);
    up[v] = add(up[u], mult(bigmod(10, hi[u]), w));
    hi[v] = hi[u] + 1;
    prep(v, u, cent);
  }
}
long long solve(int cent) {
  for (int i = 0; i < nodes.size(); i++) {
    up[nodes[i]] = 0;
    down[nodes[i]] = 0;
    hi[nodes[i]] = 0;
  }
  parts = 0;
  prep(cent, -1, cent);
  parts--;
  dppart[cent] = -1;
  map<long long, long long> tot;
  vector<map<long long, long long> > vec;
  vec.resize(parts + 1);
  tot[0]++;
  for (int i = 0; i < nodes.size(); i++) {
    int u = nodes[i];
    if (u == cent) continue;
    tot[up[u]]++;
    vec[dppart[u]][up[u]]++;
  }
  long long ans = 0;
  for (int i = 0; i < nodes.size(); i++) {
    int u = nodes[i];
    int ht = hi[u];
    int pt = dppart[u];
    if (u == cent) {
      ans += (tot[0] - 1);
    } else {
      long long val = ((-down[u]) % MOD + MOD) % MOD;
      val = mult(val, inv(bigmod(10, ht)));
      ans += (tot[val] - vec[pt][val]);
    }
  }
  return ans;
}
long long compsolve(int u) {
  dfs(u, -1);
  int cent = findCent(u, -1);
  long long ans = solve(cent);
  vis[cent] = true;
  for (int i = 0; i < graph[cent].size(); i++) {
    int v = graph[cent][i].first;
    if (!vis[v]) ans += compsolve(v);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> MOD;
  sieve();
  PHI = phi(MOD);
  if (MOD == 1) {
    cout << (long long)n * (n - 1) << endl;
    return 0;
  }
  for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    graph[u].push_back(make_pair(v, w));
    graph[v].push_back(make_pair(u, w));
  }
  cout << compsolve(0) << endl;
  return 0;
}
