#include <bits/stdc++.h>
using namespace std;
int const N = 100005;
int const MAXX = 1000000009;
map<int, int> Count;
vector<pair<int, int> > a[N];
int Cnt[N], Chose[N], Par[N], High[N];
int n, M, Val[N], Phi, Pow[N], Inv[N];
long long ans = 0;
void Find_Center(int u, int par, int &Center, int &Value, int &Size) {
  Par[u] = -1;
  Cnt[u] = 1;
  int Max = -MAXX;
  for (int i = 0; i < a[u].size(); i++) {
    int v = a[u][i].first;
    if (v == par || Chose[v]) continue;
    Find_Center(v, u, Center, Value, Size);
    Cnt[u] += Cnt[v];
    Max = max(Max, Cnt[v]);
    Par[v] = u;
  }
  Max = max(Max, Size - Cnt[u]);
  if (Value > Max) {
    Value = Max;
    Center = u;
  }
}
int Get_Pow(int x, int y) {
  if (y == 0) return 1;
  long long u = Get_Pow(x, y / 2);
  if (y % 2)
    return u * u % M * x % M;
  else
    return u * u % M;
}
void Get_Value(int u, int par) {
  int Div = 1ll * (M - Val[u]) * Inv[High[u]] % M;
  ans += Count[Div];
  for (int i = 0; i < a[u].size(); i++) {
    int v = a[u][i].first;
    int w = a[u][i].second;
    if (Chose[v] || v == par) continue;
    High[v] = High[u] + 1;
    Val[v] = (1ll * Val[u] * 10 + w) % M;
    Get_Value(v, u);
  }
}
void Update_Set(int u, int par, int type) {
  if (type == 0)
    Count[Val[u]]++;
  else
    ans += Val[u] == 0;
  for (int i = 0; i < a[u].size(); i++) {
    int v = a[u][i].first;
    int w = a[u][i].second;
    if (Chose[v] || v == par) continue;
    Val[v] = (Val[u] + 1ll * w * Pow[High[u]] % M) % M;
    Update_Set(v, u, type);
  }
}
void Solve(int u, int Size) {
  if (Size == 1) return;
  int Center = u, Value = MAXX;
  Find_Center(u, -1, Center, Value, Size);
  Chose[Center] = 1;
  Size--;
  Count.clear();
  Count[0] = 1;
  High[Center] = 0;
  Val[Center] = 0;
  for (int i = 0; i < a[Center].size(); i++) {
    int v = a[Center][i].first;
    int w = a[Center][i].second;
    if (Chose[v]) continue;
    if (Par[Center] != v) Size -= Cnt[v];
    High[v] = 1;
    Val[v] = w % M;
    Get_Value(v, Center);
    Update_Set(v, Center, 1);
    Update_Set(v, Center, 0);
  }
  Count.clear();
  High[Center] = 0;
  Val[Center] = 0;
  for (int i = a[Center].size() - 1; i >= 0; i--) {
    int v = a[Center][i].first;
    int w = a[Center][i].second;
    if (Chose[v]) continue;
    High[v] = 1;
    Val[v] = w % M;
    Get_Value(v, Center);
    Update_Set(v, Center, 0);
  }
  for (int i = 0; i < a[Center].size(); i++) {
    int v = a[Center][i].first;
    if (Chose[v]) continue;
    if (Par[Center] != v)
      Solve(v, Cnt[v]);
    else
      Solve(v, Size);
  }
}
int Get_Phi(int Num) {
  int Copy = Num;
  int Mul = 1;
  for (int i = 2; i <= sqrt(Num); i++) {
    if (Num % i == 0) {
      Copy /= i;
      while (Num % i == 0) Num /= i;
      Mul *= (i - 1);
    }
  }
  if (Num > 1) {
    Copy /= Num;
    Mul *= (Num - 1);
  }
  return Copy * Mul;
}
int main() {
  ios_base::sync_with_stdio(0);
  int u, v, w;
  cin >> n >> M;
  Phi = Get_Phi(M);
  Pow[0] = 1;
  for (int i = 1; i <= n; i++) Pow[i] = 1ll * Pow[i - 1] * 10 % M;
  for (int i = 1; i <= n; i++) Inv[i] = Get_Pow(Pow[i], (Phi - 1));
  for (int i = 1; i < n; i++) {
    cin >> u >> v >> w;
    a[u].push_back(make_pair(v, w));
    a[v].push_back(make_pair(u, w));
  }
  Solve(0, n);
  cout << ans;
}
