#include <bits/stdc++.h>
using namespace std;
const int maxn = (1e5) + 10;
int n, mod, sz[maxn], ssz, nval[maxn], h[maxn], id[maxn], ph;
long long int ans;
bool mark[maxn];
vector<pair<int, int> > G[maxn];
vector<int> lis;
queue<int> Q;
map<long long int, int> cnt, cnt2[maxn];
int get_phi(int x) {
  long long int ans = x;
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) {
      while (x % i == 0) x /= i;
      ans /= i;
      ans *= (i - 1);
    }
  if (x > 1) ans = (ans * (x - 1)) / (x);
  return ans;
}
int pw(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (1ll * ans * a) % mod;
    b >>= 1;
    a = (1ll * a * a) % mod;
  }
  return ans % mod;
}
int taq(int a, int b) { return (1ll * a * pw(b, ph - 1)) % mod; }
void pre_DFS(int v, int p) {
  lis.push_back(v);
  sz[v] = 1, ssz++;
  for (pair<int, int> u : G[v])
    if (u.first != p && !mark[u.first]) {
      pre_DFS(u.first, v);
      sz[v] += sz[u.first];
    }
}
int get_cen(int v, int p) {
  for (pair<int, int> u : G[v])
    if (u.first != p && !mark[u.first])
      if (sz[u.first] > (ssz >> 1)) return get_cen(u.first, v);
  return v;
}
void DFS_D(int v, int p, int val) {
  for (pair<int, int> u : G[v]) {
    if (u.first == p || mark[u.first]) continue;
    h[u.first] = h[v] + 1, nval[u.first] = (1ll * val * 10 + u.second) % mod;
    DFS_D(u.first, v, nval[u.first]);
  }
}
void DFS_U(int v, int p, int idd, int val) {
  id[v] = idd, cnt[val]++, cnt2[idd][val]++;
  for (pair<int, int> u : G[v]) {
    if (u.first == p || mark[u.first]) continue;
    int num = (val + (1ll * u.second * pw(10, h[v])) % mod) % mod;
    DFS_U(u.first, v, idd, num);
  }
}
void solve(int v) {
  lis.clear();
  pre_DFS(v, -1);
  int cen = get_cen(v, -1);
  h[cen] = 0, ssz = 0;
  DFS_D(cen, -1, 0);
  for (int i = 0; i < (int)G[cen].size(); i++) {
    pair<int, int> u = G[cen][i];
    if (mark[u.first]) continue;
    DFS_U(u.first, cen, i, u.second % mod);
  }
  for (int vv : lis) {
    if (vv == cen) continue;
    int num = nval[vv], H = h[vv], val = (-1) * taq(num, pw(10, H)) % mod;
    val = (val + 2 * mod) % mod;
    ans += cnt[val] - cnt2[id[vv]][val];
    if (nval[vv] == 0) ans++;
  }
  ans += cnt[0];
  for (pair<int, int> u : G[cen])
    if (!mark[u.first]) Q.push(u.first);
  mark[cen] = 1;
  cnt.clear();
  for (int i = 0; i < (int)G[cen].size(); i++) cnt2[i].clear();
}
int32_t main() {
  cin >> n >> mod;
  for (int i = 1; i < n; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    G[x].push_back(make_pair(y, z));
    G[y].push_back(make_pair(x, z));
  }
  ph = get_phi(mod);
  Q.push(0);
  while (Q.size()) {
    solve(Q.front());
    Q.pop();
  }
  cout << ans << '\n';
}
