#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, M, sz[maxn];
int inv[maxn], mod[maxn];
long long ans;
bool mark[maxn];
map<int, int> qtd;
vector<pair<int, int> > grafo[maxn];
pair<int, int> euclid(int a, int b) {
  if (!a) return {0, 1};
  pair<int, int> P = euclid(b % a, a);
  int x = P.first, y = P.second;
  return {y - (b / a) * x, x};
}
void get_mod(void) {
  int atual = 1;
  mod[0] = 1;
  for (int i = 1; i <= n; i++) {
    atual = ((long long)atual * 10LL) % M;
    mod[i] = atual;
  }
}
void get_inv(void) {
  for (int i = 0; i <= n; i++) {
    inv[i] = euclid(mod[i], M).first;
    inv[i] = (inv[i] + M) % M;
  }
}
int dfs(int u, int p) {
  sz[u] = 1;
  for (auto P : grafo[u]) {
    int v = P.first;
    if (v == p || mark[v]) continue;
    sz[u] += dfs(v, u);
  }
  return sz[u];
}
int centroid(int u, int p, int S) {
  for (auto P : grafo[u]) {
    int v = P.first;
    if (v == p || mark[v]) continue;
    if (sz[v] > S / 2) return centroid(v, u, S);
  }
  return u;
}
void upd(int u, int p, int depth, int val, int add, int root) {
  qtd[val] += add;
  for (auto P : grafo[u]) {
    int v = P.first, d = P.second;
    if (v == p || mark[v]) continue;
    int aux = ((long long)d * (long long)mod[depth]) % M;
    upd(v, u, depth + 1, (val + aux) % M, add, root);
  }
}
void get(int u, int p, int depth, int val) {
  int m = (-val + M) % M;
  m = ((long long)m * (long long)inv[depth]) % M;
  ans += (long long)qtd[m];
  for (auto P : grafo[u]) {
    int v = P.first, d = P.second;
    if (v == p || mark[v]) continue;
    int aux = val;
    aux = ((long long)aux * 10LL) % M;
    aux = (aux + d) % M;
    get(v, u, depth + 1, aux);
  }
}
void decompose(int u) {
  dfs(u, 0);
  int c = centroid(u, 0, sz[u]);
  mark[c] = 1;
  qtd[0]++;
  for (auto P : grafo[c]) {
    int v = P.first, d = P.second;
    if (mark[v]) continue;
    upd(v, c, 1, d, 1, c);
  }
  ans += (long long)qtd[0] - 1LL;
  for (auto P : grafo[c]) {
    int v = P.first, d = P.second;
    if (mark[v]) continue;
    upd(v, c, 1, d, -1, c);
    get(v, c, 1, d);
    upd(v, c, 1, d, 1, c);
  }
  qtd[0]--;
  for (auto P : grafo[c]) {
    int v = P.first, d = P.second;
    if (mark[v]) continue;
    upd(v, c, 1, d, -1, c);
  }
  for (auto P : grafo[c]) {
    int v = P.first;
    if (!mark[v]) decompose(v);
  }
}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> M;
  for (int i = 1; i <= n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u++, v++;
    grafo[u].push_back({v, w % M});
    grafo[v].push_back({u, w % M});
  }
  get_mod();
  get_inv();
  decompose(1);
  cout << ans << "\n";
}
