#include <bits/stdc++.h>
using namespace std;
int n;
int m;
vector<pair<int, int> > v[100002];
int sizz[100002];
bool use[100002];
inline void dfs(int b) {
  use[b] = true;
  sizz[b] = 0;
  for (int i = 0; i < v[b].size(); i++) {
    if (!use[b]) {
      dfs(v[b][i].first);
      sizz[b] += sizz[v[b][i].first];
    }
  }
}
bool cen[100002];
inline pair<int, int> cent(int b, int t, int pr) {
  pair<int, int> res = make_pair(INT_MAX, -1);
  int M = 0;
  int s = 1;
  int siz = v[b].size();
  for (int i = 0; i < siz; i++) {
    if (v[b][i].first == pr) {
      continue;
    }
    if (cen[v[b][i].first] == true) {
      continue;
    }
    res = min(res, cent(v[b][i].first, t, b));
    M = max(M, sizz[v[b][i].first]);
    s += sizz[v[b][i].first];
  }
  sizz[b] = s;
  M = max(M, t - s);
  res = min(res, make_pair(M, b));
  return res;
}
map<int, int> mp;
long long int p10[100002];
long long int inv[100002];
long long int way = 0;
vector<vector<int> > V;
inline void dfs2(int b, long long int val, int pr, vector<int> &p,
                 long long int base = 1) {
  base *= 10LL;
  if (base >= m) base %= m;
  if (val >= m) {
    val %= m;
  }
  if (val == 0LL) {
    way++;
  }
  p.emplace_back(val);
  int siz = v[b].size();
  for (int i = 0; i < siz; i++) {
    if (v[b][i].first == pr) continue;
    if (cen[v[b][i].first]) continue;
    dfs2(v[b][i].first, val + base * (long long int)(v[b][i].second), b, p,
         base);
  }
}
long long int ppow(long long int i, long long int j) {
  long long int res = 1;
  while (j) {
    if ((j & 1LL)) {
      res *= i;
      res %= m;
    }
    j >>= 1;
    i *= i;
    i %= m;
  }
  res %= m;
  return res;
}
inline void dfs3(int b, long long int val, int pr = -1, int dep = 1) {
  if (val >= m) {
    val %= m;
  }
  if (val == 0LL) {
    way++;
  }
  long long int need = m - val;
  need *= inv[dep];
  if (need >= m) need %= m;
  way += mp[need];
  int sz = v[b].size();
  for (int i = 0; i < sz; i++) {
    if (cen[v[b][i].first]) {
      continue;
    }
    if (v[b][i].first == pr) continue;
    dfs3(v[b][i].first, val * 10LL + v[b][i].second, b, dep + 1);
  }
}
vector<int> emp;
vector<int> ed;
inline void solve(int b) {
  cen[b] = true;
  int sizzz = v[b].size();
  V.clear();
  ed.clear();
  for (int i = 0; i < sizzz; i++) {
    if (cen[v[b][i].first] == true) continue;
    V.emplace_back(emp);
    ed.emplace_back(i);
    dfs2(v[b][i].first, v[b][i].second, -1, V.back());
  }
  mp.clear();
  sizzz = V.size();
  for (int i = 0; i < sizzz; i++) {
    for (int j = 0; j < V[i].size(); j++) {
      mp[V[i][j]]++;
    }
  }
  int es = ed.size();
  for (int i = 0; i < es; i++) {
    int vvv = V[i].size();
    for (int j = 0; j < vvv; j++) {
      mp[V[i][j]]--;
    }
    dfs3(v[b][ed[i]].first, v[b][ed[i]].second, -1);
    for (int j = 0; j < vvv; j++) {
      mp[V[i][j]]++;
    }
  }
  int siz = v[b].size();
  for (int i = 0; i < siz; i++) {
    int go = v[b][i].first;
    if (cen[go] == false) {
      solve(cent(go, sizz[go], b).second);
    }
  }
}
long long int extgcd(long long int a, long long int b, long long int &x,
                     long long int &y) {
  long long int d = a;
  if (b != 0) {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}
long long int modinverse(long long int a, long long int b) {
  long long int x, y;
  long long int d = extgcd(a, b, x, y);
  return (x % b + b) % b;
}
int main() {
  cin >> n >> m;
  if (m == 1) {
    long long int ans = n;
    ans *= (long long int)(n - 1);
    printf("%I64d\n", ans);
    return 0;
  }
  p10[0] = 1;
  for (int i = 1; i < 100002; i++) {
    p10[i] = p10[i - 1];
    p10[i] *= 10LL;
    p10[i] %= m;
  }
  for (int i = 0; i < 100002; i++) {
    inv[i] = modinverse(p10[i], m);
  }
  for (int i = 1; i < n; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    v[a].emplace_back(make_pair(b, c));
    v[b].emplace_back(make_pair(a, c));
  }
  dfs(0);
  solve(cent(0, n, -1).second);
  printf("%lld\n", way);
  return 0;
}
