#include <bits/stdc++.h>
using namespace std;
const int N = 100011;
struct Edge {
  int v, d, num;
  bool f;
  Edge(int v, int d, int num, int f) : v(v), d(d), num(num), f(f){};
  Edge(){};
};
int n, M;
vector<Edge> G[N];
int cnt[N], h[N];
int C;
map<int, int> mp[N];
int pw[N];
long long ans;
int p[N];
void dfs(int v, int p) {
  cnt[v] = 1;
  for (int i = 0; i < G[v].size(); ++i) {
    int to = G[v][i].v;
    if (to == p || G[v][i].f == false) {
      continue;
    }
    dfs(to, v);
    cnt[v] += cnt[to];
  }
}
void init(int v, int p) {
  h[v] = (p == -1 ? 0 : h[p] + 1);
  for (int i = 0; i < G[v].size(); ++i) {
    int to = G[v][i].v;
    if (to == p || G[v][i].f == false) {
      continue;
    }
    init(to, v);
  }
}
int find(int v, int p) {
  for (int i = 0; i < G[v].size(); ++i) {
    int to = G[v][i].v;
    if (to == p || G[v][i].f == false) {
      continue;
    }
    if (2 * cnt[to] > C) return find(to, v);
  }
  return v;
}
int getX(int d, int h) {
  d = (-d + M) % M;
  return 1ll * d * p[h] % M;
}
void calcUp(int v, int p, int num, int last, int digit) {
  int x = (1ll * digit * pw[h[v] - 1] + last) % M;
  if (x == 0) {
    ans++;
  }
  mp[num][x]++;
  mp[0][x]++;
  for (int i = 0; i < G[v].size(); ++i) {
    int to = G[v][i].v;
    if (to == p || G[v][i].f == false) {
      continue;
    }
    calcUp(to, v, num, x, G[v][i].d);
  }
}
void calcDown(int v, int p, int num, int last, int digit) {
  int value = (1ll * 10 * last + digit) % M;
  int x = getX(value, h[v]);
  ans += mp[0][x] - mp[num][x];
  for (int i = 0; i < G[v].size(); ++i) {
    int to = G[v][i].v;
    if (to == p || G[v][i].f == false) {
      continue;
    }
    calcDown(to, v, num, value, G[v][i].d);
  }
}
int phi(int x) {
  int result = x;
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      while (x % i == 0) {
        x /= i;
      }
      result -= result / i;
    }
  }
  if (x > 1) result -= result / x;
  return result;
}
int binPow(int a, int n) {
  int result = 1;
  while (n > 0) {
    if (n % 2 == 1) result = 1ll * result * a % M;
    n /= 2;
    a = 1ll * a * a % M;
  }
  return result;
}
void solve(int v) {
  dfs(v, -1);
  C = cnt[v];
  if (C == 1) {
    return;
  }
  int centr = find(v, -1);
  init(centr, -1);
  int size = 1;
  mp[0][0] = 1;
  for (int i = 0; i < G[centr].size(); ++i) {
    if (G[centr][i].f == false) {
      continue;
    }
    calcUp(G[centr][i].v, centr, size, 0, G[centr][i].d);
    size++;
  }
  size = 1;
  for (int i = 0; i < G[centr].size(); ++i) {
    if (G[centr][i].f == false) {
      continue;
    }
    calcDown(G[centr][i].v, centr, size, 0, G[centr][i].d);
    size++;
  }
  for (int i = 0; i < size; ++i) {
    mp[i].clear();
  }
  for (int i = 0; i < G[centr].size(); ++i) {
    if (G[centr][i].f == false) {
      continue;
    }
    G[centr][i].f = false;
    G[G[centr][i].v][G[centr][i].num].f = false;
    solve(G[centr][i].v);
  }
}
int main() {
  scanf("%d%d", &n, &M);
  pw[0] = 1;
  for (int i = 1; i < N; ++i) {
    pw[i] = 1ll * pw[i - 1] * 10 % M;
  }
  int v = phi(M);
  p[1] = binPow(10, v - 1);
  for (int i = 2; i < N; ++i) {
    p[i] = 1ll * p[i - 1] * p[1] % M;
  }
  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    G[u].push_back(Edge(v, w, G[v].size(), true));
    G[v].push_back(Edge(u, w, G[u].size() - 1, true));
  }
  solve(0);
  cout << ans << endl;
  return 0;
}
