#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<pair<int, int>> G[N];
bool ban[N];
int sz[N];
vector<int> all;
int tot, M;
void dfs1(int x, int p) {
  sz[x] = 1;
  all.push_back(x);
  for (auto uw : G[x]) {
    int u = uw.first, w = uw.second;
    if (u == p || ban[u]) continue;
    dfs1(u, x);
    sz[x] += sz[u];
  }
}
int root, REV;
void dfs2(int x, int p) {
  int out = tot - sz[x];
  for (auto uw : G[x]) {
    int u = uw.first, w = uw.second;
    if (u == p || ban[u]) continue;
    dfs2(u, x);
    out = max(out, sz[u]);
  }
  if (out * 2 <= tot) root = x;
}
map<int, int> need;
vector<int> add;
long long ans = 0;
void dfs3(int x, int p, int b, int bb, int pp) {
  if (b == 0) ans++;
  if (bb == 0) ans++;
  for (auto uw : G[x]) {
    int u = uw.first, w = uw.second;
    if (u == p || ban[u]) continue;
    dfs3(u, x, (b * 10LL + w) % M, (bb + 1LL * w * pp) % M, pp * 10LL % M);
  }
}
int mpow(int x, int n) {
  int res = 1;
  while (n) {
    if (n & 1) res = 1LL * res * x % M;
    n >>= 1;
    x = 1LL * x * x % M;
  }
  return res;
}
void dfs4(int x, int p, int k, int pp, int len, int b) {
  if (need.count(k)) ans += need[k];
  add.push_back(1LL * (M - b) * mpow(REV, len) % M);
  for (auto uw : G[x]) {
    int u = uw.first, w = uw.second;
    if (u == p || ban[u]) continue;
    dfs4(u, x, (k + 1LL * w * pp) % M, pp * 10LL % M, len + 1,
         (b * 10LL + w) % M);
  }
}
void divide(int x) {
  all.clear();
  dfs1(x, -1);
  tot = sz[x];
  dfs2(x, -1);
  x = root;
  for (auto u : G[x]) {
    if (ban[u.first]) continue;
    dfs3(u.first, x, u.second % M, u.second % M, 10 % M);
  }
  need.clear();
  vector<pair<int, int>> tmp;
  for (auto u : G[x]) {
    if (ban[u.first]) continue;
    tmp.push_back(u);
    add.clear();
    dfs4(u.first, x, u.second % M, 10 % M, 1, u.second % M);
    for (int x : add) ++need[x];
  }
  reverse(tmp.begin(), tmp.end());
  need.clear();
  for (auto u : tmp) {
    if (ban[u.first]) continue;
    add.clear();
    dfs4(u.first, x, u.second % M, 10 % M, 1, u.second % M);
    for (int x : add) ++need[x];
  }
  ban[root] = 1;
  for (auto u : tmp) {
    if (ban[u.first]) continue;
    divide(u.first);
  }
}
int exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  int t, ret;
  ret = exgcd(b, a % b, x, y);
  t = x;
  x = y;
  y = t - a / b * y;
  return ret;
}
int main() {
  int n, y;
  scanf("%d%d", &n, &M);
  exgcd(10, M, REV, y);
  ((REV %= M) += M) %= M;
  for (int i = 0; i < n - 1; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    G[u].push_back(make_pair(v, w));
    G[v].push_back(make_pair(u, w));
  }
  divide(1);
  cout << ans << endl;
}
