#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:64000000")
const double pi = 3.14159265358979323846;
const double eps = 1e-6;
const long long maxn = 200051;
const long long inf = 1000000007;
const long long mod = 1000000007;
long long m, w;
long long bpow(long long x, long long n) {
  if (n == 0) return 1;
  if (n % 2 == 1)
    return (x * bpow(x, n - 1)) % m;
  else {
    long long tans = bpow(x, n / 2);
    return (tans * tans) % m;
  }
}
int n, x, y;
long long st[maxn], st1[maxn], ans;
vector<pair<int, long long> > v[maxn];
pair<unordered_map<long long, long long>, unordered_map<long long, long long> >
    ma[maxn];
int dfs(int ver, long long a, long long b, long long d = 0, int pr = -1) {
  int now = ver;
  ma[now].first[a]++;
  ma[now].second[(b * st1[d]) % m]++;
  for (int i = 0; i < v[ver].size(); i++) {
    if (v[ver][i].first == pr) continue;
    long long ta = (a + (v[ver][i].second * st[d]) % m) % m;
    long long tb = ((b * 10) % m + v[ver][i].second) % m;
    int p = dfs(v[ver][i].first, ta, tb, d + 1, ver);
    if (ma[p].first.size() > ma[now].first.size()) {
      swap(now, p);
    }
    for (auto it = ma[p].first.begin(); it != ma[p].first.end(); it++) {
      long long cur = it->first;
      long long cnt = it->second;
      cur = cur - a;
      if (cur < 0) cur += m;
      cur = (cur * st1[2 * d]) % m;
      cur = -cur;
      if (cur < 0) cur += m;
      cur = (cur + (b * st1[d]) % m) % m;
      if (ma[now].second.count(cur)) {
        ans += cnt * (ma[now].second[cur]);
      }
    }
    for (auto it = ma[p].second.begin(); it != ma[p].second.end(); it++) {
      long long cur = it->first;
      long long cnt = it->second;
      cur = cur - (b * st1[d]) % m;
      if (cur < 0) cur += m;
      cur = (cur * st[2 * d]) % m;
      cur = -cur;
      if (cur < 0) cur += m;
      cur = (cur + a) % m;
      if (ma[now].first.count(cur)) {
        ans += cnt * (ma[now].first[cur]);
      }
    }
    for (auto it = ma[p].first.begin(); it != ma[p].first.end(); it++) {
      ma[now].first[it->first] += it->second;
    }
    for (auto it = ma[p].second.begin(); it != ma[p].second.end(); it++) {
      ma[now].second[it->first] += it->second;
    }
  }
  return now;
}
long long fi(long long mo) {
  long long z = mo;
  for (long long i = 2; i * i <= m; i++) {
    if (mo % i == 0) {
      z = z - z / i;
    }
    while (mo % i == 0) {
      mo /= i;
    }
  }
  if (mo != 1) {
    z = z - z / mo;
  }
  return z;
}
int main() {
  scanf("%d %I64d", &n, &m);
  for (int i = 0; i < n - 1; i++) {
    scanf("%d %d %I64d", &x, &y, &w);
    v[x].push_back(make_pair(y, w));
    v[y].push_back(make_pair(x, w));
  }
  if (m == 0) {
    cout << (long long)n * ((long long)n - 1);
    return 0;
  }
  st[0] = 1;
  for (int i = 1; i < maxn; i++) {
    st[i] = (st[i - 1] * 10) % m;
  }
  long long tmp = bpow(10, fi(m) - 1);
  st1[0] = 1;
  for (int i = 1; i < maxn; i++) {
    st1[i] = (st1[i - 1] * tmp) % m;
  }
  dfs(0, 0, 0);
  printf("%I64d", ans);
  return 0;
}
