#include <bits/stdc++.h>
using namespace std;
const unsigned long long BASE = 107;
const long long LINF = 1e16 + 7;
const int N = 1e5 + 7;
const int INF = 1e9 + 7;
const int MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-8;
int n, m, q[N], f[N], msz[N], siz[N], pw[N], rpw[N];
bool vis[N];
long long cnt1, cnt2;
map<int, int> R;
vector<pair<int, int> > e[N];
long long kpow(long long a, long long b, long long mod) {
  long long r = 1;
  while (b > 0) {
    if (b & 1) r = r * a % mod;
    a = a * a % mod, b >>= 1;
  }
  return r;
}
int find(int u) {
  int t = 1;
  q[0] = u, f[u] = -1;
  for (int h = (0); h < (t); ++h) {
    u = q[h];
    msz[u] = 0, siz[u] = 1;
    for (int i = (0); i < (((int)(e[u]).size())); ++i) {
      int v = e[u][i].first;
      if (vis[v] || v == f[u]) continue;
      f[v] = u, q[t++] = v;
    }
  }
  for (int h = t - 1; h >= 0; --h) {
    u = q[h];
    msz[u] = max(msz[u], t - siz[u]);
    if (msz[u] * 2 <= t) return u;
    if (~f[u]) {
      siz[f[u]] += siz[u];
      msz[f[u]] = max(msz[f[u]], siz[u]);
    }
  }
  return 0;
}
void dfs1(int u, int w, int d, int p) {
  cnt1 += w == 0;
  cnt2 += R[1ll * (m - w) * rpw[d] % m];
  for (int i = (0); i < (((int)(e[u]).size())); ++i) {
    int v = e[u][i].first;
    if (vis[v] || v == p) continue;
    dfs1(v, (1ll * 10 * w + e[u][i].second) % m, d + 1, u);
  }
}
void dfs2(int u, int w, int d, int p) {
  cnt1 += w == 0;
  ++R[w];
  for (int i = (0); i < (((int)(e[u]).size())); ++i) {
    int v = e[u][i].first;
    if (vis[v] || v == p) continue;
    dfs2(v, (1ll * e[u][i].second * pw[d] + w) % m, d + 1, u);
  }
}
void solve(int u) {
  u = find(u);
  R.clear();
  for (int i = (0); i < (((int)(e[u]).size())); ++i) {
    int v = e[u][i].first;
    if (vis[v]) continue;
    dfs1(v, e[u][i].second % m, 1, u);
    dfs2(v, e[u][i].second % m, 1, u);
  }
  reverse(e[u].begin(), e[u].end());
  R.clear();
  for (int i = (0); i < (((int)(e[u]).size())); ++i) {
    int v = e[u][i].first;
    if (vis[v]) continue;
    dfs1(v, e[u][i].second % m, 1, u);
    dfs2(v, e[u][i].second % m, 1, u);
  }
  vis[u] = true;
  for (int i = (0); i < (((int)(e[u]).size())); ++i)
    if (!vis[e[u][i].first]) solve(e[u][i].first);
}
int phi(int n) {
  int ret = n;
  for (int i = 2, I = sqrt(n + 0.5); i <= I; ++i)
    if (n % i == 0) {
      ret = ret / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ret = ret / n * (n - 1);
  return ret;
}
void init(int n) {
  int inv = kpow(10, phi(m) - 1, m);
  pw[0] = rpw[0] = 1;
  for (int i = (1); i < (n + 1); ++i) {
    pw[i] = 1ll * 10 * pw[i - 1] % m;
    rpw[i] = 1ll * inv * rpw[i - 1] % m;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  init(n);
  for (int i = (1); i < (n); ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    e[u].push_back(make_pair(v, w)), e[v].push_back(make_pair(u, w));
  }
  memset(vis, false, sizeof(vis[0]) * n);
  cnt1 = cnt2 = 0;
  solve(0);
  printf("%I64d", cnt1 / 2 + cnt2);
  return 0;
}
