#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e5 + 7;
const long long INF = 1e9 + 7;
const long long mlog = 20;
const long long SQ = 400;
long long tav10[maxn];
long long inv10[maxn];
long long mod;
long long calc(vector<long long> &vecin,
               vector<pair<long long, long long> > vecout) {
  map<long long, long long> mp;
  for (long long x : vecin) mp[x]++;
  long long res = 0;
  for (pair<long long, long long> p : vecout)
    res += mp[(mod - p.second) * inv10[p.first] % mod];
  return res;
}
long long n, m, k;
long long ans;
bool dead[maxn];
long long sz[maxn], h[maxn];
long long val_down[maxn], val_up[maxn];
vector<long long> G[maxn];
vector<pair<long long, long long> > G2[maxn];
long long dfs_sz(long long node, long long par) {
  sz[node] = 1;
  for (long long i : G[node])
    if (!dead[i] && i != par) sz[node] += dfs_sz(i, node);
  return sz[node];
}
long long centroid(long long node, long long par, long long n) {
  for (long long v : G[node])
    if (sz[v] * 2 > n && v != par && !dead[v]) return centroid(v, node, n);
  return node;
}
void dfs_path(long long node, long long par, vector<long long> &vecin,
              vector<pair<long long, long long> > &vecout) {
  vecin.push_back(val_up[node]);
  vecout.push_back({h[node] = h[par] + 1, val_down[node]});
  for (pair<long long, long long> p : G2[node]) {
    if (p.first != par && !dead[p.first]) {
      val_up[p.first] = (tav10[h[node]] * p.second + val_up[node]) % mod;
      val_down[p.first] = (val_down[node] * 10ll + p.second) % mod;
      dfs_path(p.first, node, vecin, vecout);
    }
  }
}
void solve(long long node) {
  dfs_sz(node, node);
  long long root = centroid(node, node, sz[node]);
  dead[root] = 1;
  h[root] = 0;
  vector<long long> vecin;
  vector<pair<long long, long long> > vecout;
  for (pair<long long, long long> p : G2[root]) {
    if (!dead[p.first]) {
      long long v = p.first;
      long long w = p.second;
      val_down[v] = val_up[v] = w;
      vector<long long> vecin_tmp;
      vector<pair<long long, long long> > vecout_tmp;
      dfs_path(v, root, vecin_tmp, vecout_tmp);
      ans -= calc(vecin_tmp, vecout_tmp);
      for (long long tmp : vecin_tmp) vecin.push_back(tmp);
      for (pair<long long, long long> tmp : vecout_tmp) vecout.push_back(tmp);
    }
  }
  vecin.push_back(0);
  vecout.push_back({0, 0});
  ans += calc(vecin, vecout) - 1;
  for (long long v : G[root])
    if (!dead[v]) solve(v);
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
  ;
  cin >> n >> mod;
  tav10[0] = inv10[0] = 1;
  for (long long i = 1; i < maxn; i++) tav10[i] = tav10[i - 1] * 10 % mod;
  for (long long i = 1; i < 11; i++)
    if ((i * mod + 1) % 10 == 0) inv10[1] = (i * mod + 1) / 10;
  for (long long i = 2; i < maxn; i++) inv10[i] = inv10[1] * inv10[i - 1] % mod;
  for (long long i = 1; i < n; i++) {
    long long u, v, w;
    cin >> u >> v >> w;
    w %= mod;
    G[++u].push_back(++v);
    G[v].push_back(u);
    G2[u].push_back({v, w});
    G2[v].push_back({u, w});
  }
  solve(1);
  cout << ans << "\n";
  return 0;
}
