#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, M, sz[N], Mc[N], Pw[N], Inv[N], dpd[N], dpu[N];
long long tot;
vector<pair<int, int> > V[N];
map<int, int> Cu[N], Cd[N];
pair<int, int> Bezo(int a, int b) {
  if (a == 1) return (make_pair(1, 0));
  auto X = Bezo(b % a, a);
  return (make_pair(X.second - b / a * X.first, X.first));
}
int Inverse(int a, int b) { return ((Bezo(a, b).first + b) % b); }
void DFS(int v, int p) {
  sz[v] = 1;
  for (auto X : V[v])
    if (X.first != p && !Mc[X.first]) DFS(X.first, v), sz[v] += sz[X.first];
}
void DFS2(int v, int p, int h, int cp) {
  Cd[cp][dpd[v]]++;
  Cd[0][dpd[v]]++;
  Cu[cp][dpu[v]]++;
  Cu[0][dpu[v]]++;
  for (auto X : V[v])
    if (X.first != p && !Mc[X.first]) {
      dpd[X.first] = (1ll * dpd[v] * 10 + X.second) % M;
      dpu[X.first] = (1ll * Pw[h] * X.second + dpu[v]) % M;
      DFS2(X.first, v, h + 1, cp);
    }
}
void DFS3(int v, int p, int h, int cp) {
  tot += Cu[0][(-1ll * dpd[v] * Inv[h] % M + M) % M] -
         Cu[cp][(-1ll * dpd[v] * Inv[h] % M + M) % M];
  for (auto X : V[v])
    if (X.first != p && !Mc[X.first]) DFS3(X.first, v, h + 1, cp);
}
void Solve(int v) {
  dpd[v] = dpu[v] = 0;
  for (int i = 0; i < V[v].size(); i++)
    if (!Mc[V[v][i].first])
      dpd[V[v][i].first] = dpu[V[v][i].first] = V[v][i].second % M,
      DFS2(V[v][i].first, v, 1, i + 1);
  for (int i = 0; i < V[v].size(); i++)
    if (!Mc[V[v][i].first])
      tot += Cd[i + 1][0] + Cu[i + 1][0], DFS3(V[v][i].first, v, 1, i + 1);
  for (int i = 0; i <= V[v].size(); i++) Cu[i].clear(), Cd[i].clear();
}
int GetCentroid(int v, int p = -1, int _n = -1) {
  if (p == -1) DFS(v, p), _n = sz[v];
  for (auto X : V[v])
    if (X.first != p && !Mc[X.first] && 2 * sz[X.first] > _n)
      return (GetCentroid(X.first, v, _n));
  return (v);
}
void Decompose(int v) {
  v = GetCentroid(v);
  Solve(v);
  Mc[v] = 1;
  for (auto X : V[v])
    if (!Mc[X.first]) Decompose(X.first);
}
int main() {
  scanf("%d%d", &n, &M);
  if (M == 1) return !printf("%I64d", 1ll * n * (n - 1));
  for (int i = 1, v, u, w; i < n; i++)
    scanf("%d%d%d", &v, &u, &w), V[v + 1].push_back({u + 1, w}),
        V[u + 1].push_back({v + 1, w});
  for (int i = Pw[0] = 1; i <= n; i++)
    Pw[i] = 1ll * Pw[i - 1] * 10 % M, Inv[i] = Inverse(Pw[i], M);
  Decompose(1);
  return !printf("%I64d", tot);
}
