#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll mod = 1111111111;
const ll oo = 3372036000000000;
const ll si = 100005;
vector<pair<ll, ll>> g[si];
vector<ll> sz(si), par(si, -1), ex(si), iex(si);
ll n, m, ttn;
bitset<si> ded;
ll ans = 0;
ll phi(ll n) {
  ll result = n;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      result -= result / i;
    }
  }
  if (n > 1) result -= result / n;
  return result;
}
void fsi(ll v) {
  for (pair<ll, ll> r : g[v]) {
    if (r.first == par[v]) continue;
    par[r.first] = v;
    fsi(r.first);
    sz[v] += 1 + sz[r.first];
  }
  return;
}
void count(ll v, ll p, ll head, ll dep, ll r1, unordered_map<ll, ll> &rec,
           vector<unordered_map<int, int>> &cur) {
  if (r1 == 0) ans += 1;
  ll d1 = (m + (-r1 * iex[dep]) % m) % m;
  if (rec.count(d1)) ans += (rec[d1] - cur[head][d1]);
  for (pair<ll, ll> r : g[v]) {
    if (ded[r.first] || r.first == p) continue;
    ll nr1 = ((r1 * 10) + r.second) % m;
    count(r.first, v, head, dep + 1, nr1, rec, cur);
  }
}
void update(ll v, ll p, ll head, ll dep, ll r1, unordered_map<ll, ll> &rec,
            vector<unordered_map<int, int>> &cur) {
  if (r1 == 0) ans += 1;
  rec[r1] += 1;
  cur[head][r1] += 1;
  for (pair<ll, ll> r : g[v]) {
    if (r.first == p || ded[r.first]) continue;
    ll nr1 = ((r.second * ex[dep]) + r1) % m;
    update(r.first, v, head, dep + 1, nr1, rec, cur);
  }
  return;
}
void dodo(ll cen) {
  int in = 0;
  unordered_map<ll, ll> rec, track;
  vector<unordered_map<int, int>> cur;
  for (pair<ll, ll> r : g[cen]) {
    if (ded[r.first]) continue;
    int head = in;
    track[r.first] = in++;
    cur.push_back({});
    update(r.first, cen, head, 1, r.second, rec, cur);
  }
  for (pair<ll, ll> r : g[cen]) {
    if (ded[r.first]) continue;
    int head = track[r.first];
    count(r.first, cen, head, 1, r.second, rec, cur);
  }
  return;
}
void decompose(ll v, ll bu) {
  ll cen = v;
  while (1) {
    ll nc = -1;
    for (pair<ll, ll> r : g[cen]) {
      if (r.first == par[cen] || ded[r.first]) continue;
      if ((sz[r.first] + 1) * 2 > bu) nc = r.first;
    }
    if ((bu - 1 - sz[cen]) * 2 > bu && par[cen] != -1 && !ded[par[cen]])
      nc = par[cen];
    if (nc == -1)
      break;
    else
      cen = nc;
  }
  for (ll u = par[cen]; u != -1 && !ded[u]; u = par[u]) sz[u] -= (1 + sz[cen]);
  ded[cen] = 1;
  dodo(cen);
  for (pair<ll, ll> r : g[cen]) {
    if (ded[r.first]) continue;
    ll nbu = sz[r.first] + 1;
    if (r.first == par[cen]) nbu = bu - sz[cen] - 1;
    decompose(r.first, nbu);
  }
  return;
}
ll inv(ll a) {
  ll b = ttn - 1;
  ll ans = 1;
  while (b > 0) {
    if (b & 1) ans = (ans * a) % m;
    a = (a * a) % m;
    b >>= 1;
  }
  return ans;
}
void ini() {
  ttn = phi(m);
  ex[0] = 1;
  iex[0] = 1;
  for (ll i = 1; i <= n; i++) {
    ex[i] = (ex[i - 1] * 10) % m;
    iex[i] = inv(ex[i]);
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  ini();
  for (ll i = 1; i < n; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    if (c >= m) c %= m;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  fsi(0);
  decompose(0, n);
  cout << ans << "\n";
  return 0;
}
