#include <bits/stdc++.h>
using namespace std;
long long mod;
vector<pair<long long, long long> > pat[100000];
vector<pair<long long, long long> > ko[100000];
pair<long long, long long> par[100000];
map<long long, long long> du[100000];
map<long long, long long> dl[100000];
long long mlu[100000], plu[100000];
long long mld[100000], pld[100000];
bool flag[100000];
void dfs(int node) {
  if (flag[node]) return;
  flag[node] = true;
  for (int i = 0; i < pat[node].size(); i++) {
    if (!flag[pat[node][i].first]) {
      ko[node].push_back(pat[node][i]);
      par[pat[node][i].first] = make_pair(node, pat[node][i].second);
      dfs(pat[node][i].first);
    }
  }
}
long long ans = 0;
long long p10[200001];
long long pv10[200001];
int calc(int node) {
  du[node][0] = 1;
  dl[node][0] = 1;
  mlu[node] = 0, plu[node] = 0;
  mld[node] = 0, pld[node] = 0;
  int now = node;
  for (int i = 0; i < ko[node].size(); i++) {
    int z = calc(ko[node][i].first);
    if (du[now].size() < du[z].size()) swap(now, z);
    map<long long, long long>::iterator it = du[z].begin();
    for (;;) {
      if (it == du[z].end()) break;
      long long x = (*it).first, k = (*it).second;
      long long mok = (mod - (x * p10[mlu[z]] + plu[z]) % mod) % mod;
      mok = (mok + mod - pld[now]) * p10[mld[now]] % mod;
      if (dl[now].count(mok)) ans += dl[now][mok] * k;
      it++;
    }
    it = dl[z].begin();
    for (;;) {
      if (it == dl[z].end()) break;
      long long x = (*it).first, k = (*it).second;
      long long mok = (mod - (x * pv10[mld[z]] + pld[z]) % mod) % mod;
      mok = (mok + mod - plu[now]) * pv10[mlu[now]] % mod;
      if (du[now].count(mok)) ans += du[now][mok] * k;
      it++;
    }
    it = du[z].begin();
    for (;;) {
      if (it == du[z].end()) break;
      long long x = (*it).first, k = (*it).second;
      x = (x * p10[mlu[z]] + plu[z]) % mod;
      x = (x + mod - plu[now]) * pv10[mlu[now]] % mod;
      du[now][x] += k;
      it++;
    }
    it = dl[z].begin();
    for (;;) {
      if (it == dl[z].end()) break;
      long long x = (*it).first, k = (*it).second;
      x = (x * pv10[mld[z]] + pld[z]) % mod;
      x = (x + mod - pld[now]) * p10[mld[now]] % mod;
      dl[now][x] += k;
      it++;
    }
  }
  mlu[now]++;
  plu[now] = (plu[now] * 10 + par[node].second) % mod;
  mld[now]++;
  pld[now] = ((pld[now] + par[node].second) * pv10[1]) % mod;
  return now;
}
int main() {
  int num;
  scanf("%d%I64d", &num, &mod);
  for (int i = 0; i < num - 1; i++) {
    int za, zb, zc;
    scanf("%d%d%d", &za, &zb, &zc);
    pat[za].push_back(make_pair(zb, zc));
    pat[zb].push_back(make_pair(za, zc));
  }
  long long inv;
  for (long long i = 0;; i++) {
    if ((mod * i + 1) % 10 == 0) {
      inv = (mod * i + 1) / 10;
      break;
    }
  }
  p10[0] = pv10[0] = 1;
  for (int i = 1; i <= 200000; i++)
    p10[i] = (p10[i - 1]) * 10 % mod, pv10[i] = (pv10[i - 1] * inv) % mod;
  dfs(0);
  calc(0);
  printf("%I64d\n", ans);
}
