#include <bits/stdc++.h>
using namespace std;
void fre() {
  freopen("c://test//input.in", "r", stdin);
  freopen("c://test//output.out", "w", stdout);
}
template <class T1, class T2>
inline void gmax(T1 &a, T2 b) {
  if (b > a) a = b;
}
template <class T1, class T2>
inline void gmin(T1 &a, T2 b) {
  if (b < a) a = b;
}
const int N = 1e5 + 10, inf = 0x3f3f3f3f;
int n, Z;
long long mul[N];
long long inv[N];
vector<pair<int, int> > a[N];
int sz[N];
int mxp[N];
bool done[N];
int root;
int treesz;
map<int, int> mop;
int getsz(int x, int fa) {
  sz[x] = 1;
  for (int i = a[x].size() - 1; ~i; --i) {
    int y = a[x][i].first;
    if (y == fa || done[y]) continue;
    sz[x] += getsz(y, x);
  }
  return sz[x];
}
void getroot(int x, int fa) {
  mxp[x] = treesz - sz[x];
  for (auto &it : a[x]) {
    int y = it.first;
    if (y == fa || done[y]) continue;
    getroot(y, x);
    gmax(mxp[x], sz[y]);
  }
  if (mxp[x] < mxp[root]) root = x;
}
long long ans, sig;
void dfs1(int x, int fa, int val, int dep) {
  sig += (val == 0);
  ans += mop[(Z - val) * inv[dep] % Z];
  for (auto &it : a[x]) {
    if (it.first == fa || done[it.first]) continue;
    dfs1(it.first, x, (val * 10ll + it.second) % Z, dep + 1);
  }
}
void dfs2(int x, int fa, int val, int dep) {
  sig += (val == 0);
  ++mop[val];
  for (auto &it : a[x]) {
    if (it.first == fa || done[it.first]) continue;
    dfs2(it.first, x, (val + it.second * mul[dep]) % Z, dep + 1);
  }
}
void cal(int x) {
  mop.clear();
  for (auto &it : a[x]) {
    int y = it.first;
    if (done[y]) continue;
    int z = it.second;
    dfs1(y, x, z, 1);
    dfs2(y, x, z, 1);
  }
  reverse(a[x].begin(), a[x].end());
  mop.clear();
  for (auto &it : a[x]) {
    int y = it.first;
    if (done[y]) continue;
    int z = it.second;
    dfs1(y, x, z, 1);
    dfs2(y, x, z, 1);
  }
}
void dfz(int x) {
  treesz = getsz(x, 0);
  getroot(x, root = 0);
  cal(root);
  done[root] = 1;
  for (auto &it : a[root])
    if (!done[it.first]) dfz(it.first);
}
void exgcd(long long a, long long b, long long &d, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    d = a;
  } else {
    exgcd(b, a % b, d, y, x);
    y -= a / b * x;
  }
}
long long INV(long long a, long long Z) {
  long long x, y, d;
  exgcd(a, Z, d, x, y);
  if (d == 1)
    return (x % Z + Z) % Z;
  else
    return -1;
}
int main() {
  mxp[0] = inf;
  while (~scanf("%d%d", &n, &Z)) {
    mul[0] = 1;
    mul[1] = 10 % Z;
    inv[0] = 1;
    inv[1] = INV(10, Z);
    for (int i = 2; i <= n; ++i) {
      mul[i] = mul[i - 1] * 10 % Z;
      inv[i] = inv[i - 1] * inv[1] % Z;
    }
    for (int i = 1; i <= n; ++i) {
      a[i].clear();
      done[i] = 0;
    }
    for (int i = 1; i < n; ++i) {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      ++x;
      ++y;
      z %= Z;
      a[x].push_back({y, z});
      a[y].push_back({x, z});
    }
    ans = sig = 0;
    treesz = n;
    dfz(1);
    printf("%lld\n", ans + sig / 2);
  }
  return 0;
}
