#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 100005;
long long M, ans, subtree[MAXN], pkt[MAXN];
;
vector<pair<long long, pair<long long, long long> > > cand;
vector<pair<long long, long long> > adj[MAXN];
map<long long, long long> cnt;
bool sudah[MAXN];
long long inverse(long long x, long long mm = M) {
  x %= mm;
  long long a = 1, b = 0, c;
  while (x != 1) {
    c = mm / x;
    mm -= x * c;
    b -= a * c;
    swap(mm, x);
    swap(a, b);
  }
  return a + M;
}
void dfsSz(long long now, long long par) {
  subtree[now] = 1;
  for (auto nxt : adj[now]) {
    if (nxt.first == par || sudah[nxt.first]) continue;
    dfsSz(nxt.first, now);
    subtree[now] += subtree[nxt.first];
  }
}
long long findCentroid(long long now) {
  dfsSz(now, -1);
  long long ukuran = subtree[now];
  bool found = false;
  while (!found) {
    found = true;
    for (auto nxt : adj[now]) {
      if (sudah[nxt.first] || subtree[nxt.first] > subtree[now]) continue;
      if (subtree[nxt.first] > ukuran / 2) {
        found = false;
        now = nxt.first;
        break;
      }
    }
  }
  return now;
}
void dfs(long long now, long long par, long long depth, long long turun,
         long long naik) {
  if (turun == 0) {
    ans++;
  }
  if (naik == 0) {
    ans++;
  }
  cand.push_back({depth, {turun, naik}});
  for (auto nxt : adj[now]) {
    if (nxt.first == par || sudah[nxt.first]) continue;
    dfs(nxt.first, now, depth + 1, (turun * 10 + nxt.second) % M,
        (((pkt[depth] * nxt.second) % M) + naik) % M);
  }
}
void calculate(long long now) {
  vector<vector<pair<long long, pair<long long, long long> > > > tree;
  for (auto nxt : adj[now]) {
    if (sudah[nxt.first]) continue;
    cand.clear();
    dfs(nxt.first, now, 1, nxt.second % M, nxt.second % M);
    tree.push_back(cand);
  }
  cnt.clear();
  for (auto cnd : tree) {
    for (auto isi : cnd) {
      long long inv10 = inverse(pkt[isi.first]);
      long long target = ((M - ((isi.second.first) % M)) * inv10) % M;
      ans += cnt[target];
    }
    for (auto isi : cnd) {
      cnt[isi.second.second]++;
    }
  }
  reverse(tree.begin(), tree.end());
  cnt.clear();
  for (auto cnd : tree) {
    for (auto isi : cnd) {
      long long inv10 = inverse(pkt[isi.first]);
      long long target = ((M - ((isi.second.first) % M)) * inv10) % M;
      ans += cnt[target];
    }
    for (auto isi : cnd) {
      cnt[isi.second.second]++;
    }
  }
}
void buildCentTree(long long now) {
  now = findCentroid(now);
  sudah[now] = true;
  calculate(now);
  for (auto nxt : adj[now]) {
    if (!sudah[nxt.first]) buildCentTree(nxt.first);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n, u, v, w;
  cin >> n >> M;
  if (M == 1) {
    cout << n * (n - 1) << '\n';
    return 0;
  }
  pkt[0] = 1;
  for (long long i = 1; i <= n; i++) pkt[i] = (pkt[i - 1] * 10) % M;
  for (long long i = 1; i < n; i++) {
    cin >> u >> v >> w;
    u++;
    v++;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  buildCentTree(1);
  cout << ans << '\n';
  return 0;
}
