#include <bits/stdc++.h>
using namespace std;
int M;
const int MAX = 100001;
vector<int> _size, marked, _pow, _ipow;
vector<pair<int, int> > adjList[MAX + 1];
int getSize(int u, int p = -1) {
  _size[u] = 1;
  for (auto [v, w] : adjList[u])
    if (v != p && !marked[v]) _size[u] += getSize(v, u);
  return _size[u];
}
int getCentroid(int u, int p, int n) {
  for (auto [v, w] : adjList[u])
    if (v != p && !marked[v] && _size[v] * 2 > n) return getCentroid(v, u, n);
  return u;
}
void add(unordered_map<int, int> &aux, int u, int p, int lvl, int rem) {
  aux[rem]++;
  for (auto [v, w] : adjList[u])
    if (v != p && !marked[v])
      add(aux, v, u, lvl + 1, (int(1LL * w * _pow[lvl] % M) + rem) % M);
}
void remove(unordered_map<int, int> &aux, int u, int p, int lvl, int rem) {
  aux[rem]--;
  for (auto [v, w] : adjList[u])
    if (v != p && !marked[v])
      remove(aux, v, u, lvl + 1, (int(1LL * w * _pow[lvl] % M) + rem) % M);
}
long long count(unordered_map<int, int> &aux, int u, int p, int lvl, int rem) {
  int nxt = int(1LL * _ipow[lvl] * (M - rem) % M);
  long long ans = aux[nxt];
  for (auto [v, w] : adjList[u])
    if (v != p && !marked[v])
      ans += count(aux, v, u, lvl + 1, (rem * 10LL + w) % M);
  return ans;
}
long long solve(int u) {
  int N = getSize(u);
  u = getCentroid(u, -1, N);
  marked[u] = 1;
  unordered_map<int, int> aux;
  aux[0] = 1;
  for (auto [v, w] : adjList[u])
    if (!marked[v]) add(aux, v, u, 1, w % M);
  long long ans = aux[0] - 1;
  for (auto [v, w] : adjList[u])
    if (!marked[v]) {
      remove(aux, v, u, 1, w % M);
      ans += count(aux, v, u, 1, w % M);
      add(aux, v, u, 1, w % M);
    }
  aux.clear();
  for (auto [v, w] : adjList[u])
    if (!marked[v]) ans += solve(v);
  return ans;
}
int gcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int x1, y1;
  int d = gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - y1 * (a / b);
  return d;
}
int getInv() {
  int x, y;
  int g = gcd(10, M, x, y);
  assert(g == 1);
  return (x % M + M) % M;
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n >> M;
  _size = vector<int>(n), _pow = vector<int>(n + 1, 1),
  _ipow = vector<int>(n + 1, 1), marked = vector<int>(n + 1);
  _ipow[1] = getInv();
  _pow[1] = 10;
  for (int i = 2; i <= n; i++) {
    _pow[i] = int(1LL * _pow[i - 1] * 10 % M);
    _ipow[i] = int(1LL * _ipow[i - 1] * _ipow[1] % M);
  }
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adjList[u].push_back({v, w});
    adjList[v].push_back({u, w});
  }
  cout << solve(0) << '\n';
  return 0;
}
