#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int LG = 17;
int get_euler(int x) {
  int ret = x;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      while (x % i == 0) x /= i;
      ret = (int)((long long)(ret) * (long long)(i - 1) / (long long)(i));
    }
  }
  if (x > 1)
    ret = (int)((long long)(ret) * (long long)(x - 1) / (long long)(x));
  return ret;
}
int n, m;
long long dmod(long long x, int MOD = m) { return (x % MOD + MOD) % MOD; }
long long fe(long long x, long long p) {
  if (p == 0) return 1ll;
  long long ret = fe(x, p / 2);
  ret = dmod(ret * ret);
  if (p & 1) ret = dmod(ret * x);
  return ret;
}
long long p10[N + 5];
long long invp10[N + 5];
int totm;
set<pair<int, int> > adj[N + 5];
set<int> nadj[N + 5];
long long val[N + 5][3];
int sparse[N + 5][LG + 1];
int dep[N + 5];
void dfs1(int u, int bef = -1) {
  sparse[u][0] = bef;
  for (pair<int, int> v : adj[u]) {
    if (v.first == bef) continue;
    dep[v.first] = dep[u] + 1;
    val[v.first][0] = dmod(val[u][0] * 10ll + v.second);
    val[v.first][1] =
        dmod(val[u][1] + dmod((long long)v.second * p10[dep[v.first]]));
    dfs1(v.first, u);
  }
}
int get_par(int x, int y) {
  if (x == -1) return x;
  return sparse[x][y];
}
void make_sparse() {
  for (int i = 1; i <= LG; i++) {
    for (int j = 1; j <= n; j++) {
      sparse[j][i] = get_par(get_par(j, i - 1), i - 1);
    }
  }
}
int get_lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  int dif = dep[x] - dep[y];
  for (int i = 0; i <= LG; i++) {
    if ((1 << i) & dif) x = get_par(x, i);
  }
  if (x == y) return x;
  for (int i = LG; i >= 0; i--) {
    if (get_par(x, i) == get_par(y, i)) continue;
    x = get_par(x, i);
    y = get_par(y, i);
  }
  return get_par(x, 0);
}
long long get_path(int x, int y) {
  int atas = get_lca(x, y);
  long long awal = dmod(val[x][1] - val[atas][1]);
  awal = dmod(awal * invp10[dep[atas] + 1]);
  int pany = dep[y] - dep[atas];
  long long akhir = dmod(val[y][0] - dmod(val[atas][0] * p10[pany]));
  return dmod(dmod(awal * p10[pany]) + akhir);
}
void precom() {
  totm = get_euler(m);
  p10[0] = 1ll;
  for (int i = 1; i <= n; i++) {
    p10[i] = dmod(p10[i - 1] * 10ll);
  }
  invp10[n] = fe(p10[n], totm - 1);
  for (int i = n - 1; i >= 0; i--) {
    invp10[i] = dmod(invp10[i + 1] * 10ll);
  }
}
bool done[N + 5];
int subsz[N + 5];
int dfs2(int u, int bef = -1) {
  subsz[u] = 1;
  for (auto v : adj[u]) {
    if (v.first == bef) continue;
    if (done[v.first]) continue;
    subsz[u] += dfs2(v.first, u);
  }
  return subsz[u];
}
int find_centroid(int u, int bef, int sz) {
  for (auto v : adj[u]) {
    if (v.first == bef) continue;
    if (done[v.first]) continue;
    if (subsz[v.first] > sz / 2) return find_centroid(v.first, u, sz);
  }
  return u;
}
int make_centroid(int u) {
  dfs2(u);
  if (subsz[u] == 1) return u;
  int cen = find_centroid(u, -1, subsz[u]);
  done[cen] = 1;
  for (auto v : adj[cen]) {
    if (done[v.first]) continue;
    int nxtCen = make_centroid(v.first);
    nadj[cen].insert(nxtCen);
  }
  return cen;
}
map<int, int> simpen;
void insert(int u, int root) {
  int tmp = get_path(u, root);
  simpen[tmp]++;
  for (auto v : nadj[u]) {
    insert(v, root);
  }
}
void erase(int u, int root) {
  int tmp = get_path(u, root);
  simpen[tmp]--;
  for (auto v : nadj[u]) {
    erase(v, root);
  }
}
long long dfs3(int u, int root) {
  int atas = get_lca(u, root);
  int pan = dep[u] + dep[root] - 2 * dep[atas];
  long long cval = get_path(root, u);
  long long tar = dmod(m - cval);
  tar = dmod(tar * invp10[pan]);
  long long ret = 0ll;
  if (simpen.find(tar) != simpen.end()) ret += simpen[tar];
  for (auto v : nadj[u]) {
    ret += dfs3(v, root);
  }
  return ret;
}
long long calc(int u) {
  long long ret = 0ll;
  for (auto v : nadj[u]) {
    ret += calc(v);
  }
  simpen.clear();
  insert(u, u);
  ret += simpen[0] - 1;
  for (auto v : nadj[u]) {
    erase(v, u);
    ret += dfs3(v, u);
    insert(v, u);
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  precom();
  for (int i = 1; i < n; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u++;
    v++;
    adj[u].insert(make_pair(v, w));
    adj[v].insert(make_pair(u, w));
  }
  dep[1] = -1;
  dfs1(1);
  make_sparse();
  int root = make_centroid(1);
  long long ans = calc(root);
  printf("%lld\n", ans);
  return 0;
}
