#include <bits/stdc++.h>
using namespace std;
const long long maxN = 1e5 + 13;
long long root, sz[maxN], h[maxN], ans, val[maxN], m, n, pw[maxN], pre[maxN];
map<long long, long long> mp;
vector<long long> vec;
vector<pair<long long, long long>> adj[maxN];
bool mark[maxN], fl;
void dfs(long long v, long long p) {
  sz[v] = 1;
  for (auto a : adj[v]) {
    long long u = a.first, w = a.second;
    if (u != p && !mark[u]) {
      dfs(u, v);
      sz[v] += sz[u];
    }
  }
}
long long getpw(long long a, long long b) {
  long long ret = 1;
  for (; b; b >>= 1, a = 1ll * a * a % m)
    if (b & 1) ret = 1ll * ret * a % m;
  return ret;
}
void precomp() {
  pw[0] = 1;
  for (long long i = 1; i < n + 5; i++) pw[i] = pw[i - 1] * 10 % m;
  long long tmp = m, tot = m;
  for (long long p = 2; p * p <= tmp; p++)
    if (tmp % p == 0) {
      tot = tot / p * (p - 1);
      while (tmp % p == 0) tmp /= p;
    }
  if (tmp > 1) tot = tot / tmp * (tmp - 1);
  pre[0] = 1;
  pre[1] = getpw(10, tot - 1);
  for (long long i = 2; i < n + 5; i++) pre[i] = 1ll * pre[i - 1] * pre[1] % m;
}
void du(long long v, long long p) {
  for (auto a : adj[v]) {
    long long u = a.first, w = a.second;
    if (u != p && !mark[u]) {
      h[u] = h[v] + 1;
      val[u] = ((val[v]) + w * pw[h[v]]) % m;
      if (val[u] == 0) ans++;
      du(u, v);
    }
  }
}
void dd(long long v, long long p, long long cur) {
  if (v != root) vec.push_back(v);
  reverse(adj[v].begin(), adj[v].end());
  for (auto a : adj[v]) {
    long long u = a.first, w = a.second;
    if (u != p && !mark[u]) {
      long long nwcur = (cur * 10 + w) % m;
      long long wnt = ((1ll * pre[h[u]] * ((-nwcur) % m + m)) + m) % m;
      ans += mp[wnt];
      dd(u, v, nwcur);
      if (nwcur == 0 && fl) ans++;
      if (v == root) {
        while (vec.size()) {
          long long u = vec.back();
          vec.pop_back();
          mp[val[u]]++;
        }
      }
    }
  }
}
void calc(long long v) {
  long long tmp = ans;
  h[v] = 0;
  val[v] = 0;
  du(v, -1);
  mp.clear();
  fl = 0;
  dd(v, -1, 0);
  mp.clear();
  fl = 1;
  dd(v, -1, 0);
}
void solve(long long v) {
  dfs(v, -1);
  root = v;
  long long p = -1;
  bool fl = true;
  while (fl) {
    fl = false;
    for (auto a : adj[v]) {
      long long u = a.first;
      if (!mark[u] && u != p && sz[u] > sz[root] / 2) {
        p = v;
        v = u;
        fl = true;
        break;
      }
    }
  }
  mark[v] = true;
  root = v;
  calc(v);
  for (auto a : adj[v]) {
    long long u = a.first;
    if (!mark[u]) solve(u);
  }
}
int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  precomp();
  for (long long i = 0; i < n - 1; i++) {
    long long a, b, w;
    cin >> a >> b >> w;
    a++;
    b++;
    w %= m;
    adj[a].push_back({b, w});
    adj[b].push_back({a, w});
  }
  solve(1);
  cout << ans << endl;
}
