#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010, inf = 1 << 29;
int lhh, N, side[maxn], len[maxn << 1], nxt[maxn << 1], toit[maxn << 1];
int cnt, best, size[maxn], large[maxn];
bool vis[maxn];
long long _10[maxn], inv[maxn], ans;
map<int, int> M;
inline long long exgcd(long long a, long long b, long long c) {
  if (a == 0)
    return -1;
  else if (c % a == 0)
    return c / a;
  long long t = exgcd(b % a, a, ((-c % a) + a) % a);
  if (t == -1) return -1;
  return (t * b + c) / a;
}
struct Value {
  long long up, down;
  int dep;
  inline Value() {}
  inline Value(long long _up, long long _down, int _dep)
      : up(_up), down(_down), dep(_dep) {}
  inline Value merge(int w) const {
    return Value((up + w * _10[dep]) % lhh, (down * 10 + w) % lhh, dep + 1);
  }
};
vector<Value> vec[maxn];
inline void add(int a, int b, int c) {
  nxt[++cnt] = side[a];
  side[a] = cnt;
  toit[cnt] = b;
  len[cnt] = c;
}
inline void ins(int a, int b, int c) {
  add(a, b, c);
  add(b, a, c);
}
inline int gi() {
  char ch;
  int ret = 0, f = 1;
  do ch = getchar();
  while (!(ch >= '0' && ch <= '9') && ch != '-');
  if (ch == '-') f = -1, ch = getchar();
  do ret = ret * 10 + ch - '0', ch = getchar();
  while (ch >= '0' && ch <= '9');
  return ret * f;
}
inline void getroot(int now, int fa, int rest) {
  size[now] = 1;
  large[now] = 0;
  for (int i = side[now]; i; i = nxt[i]) {
    if (toit[i] == fa || vis[toit[i]]) continue;
    getroot(toit[i], now, rest);
    size[now] += size[toit[i]];
    large[now] = max(large[now], size[toit[i]]);
  }
  large[now] = max(large[now], rest - size[now]);
  if (large[now] < large[best]) best = now;
}
inline int find_root(int now, int rest) {
  best = 0;
  getroot(now, 0, rest);
  return best;
}
inline void dfs(int now, int fa, const Value &val, vector<Value> &vc) {
  size[now] = 1;
  vc.push_back(val);
  for (int i = side[now]; i; i = nxt[i])
    if (toit[i] != fa && !vis[toit[i]]) {
      dfs(toit[i], now, val.merge(len[i]), vc);
      size[now] += size[toit[i]];
    }
}
inline void cut(int now) {
  vis[now] = true;
  int num = 0;
  for (int i = side[now]; i; i = nxt[i]) {
    if (vis[toit[i]]) continue;
    vec[++num].clear();
    dfs(toit[i], now, Value(0, 0, 0).merge(len[i]), vec[num]);
  }
  M.clear();
  for (int i = 1; i <= num; ++i)
    for (auto x : vec[i]) {
      if (!x.up) ++ans;
      if (!x.down) ++ans;
      auto it = M.find((int)x.up);
      if (it == M.end())
        M[(int)x.up] = 1;
      else
        it->second++;
    }
  for (int i = 1; i <= num; ++i) {
    for (auto x : vec[i]) M[x.up]--;
    for (auto x : vec[i]) {
      auto it = M.find((int)(lhh - x.down) * inv[x.dep] % lhh);
      if (it != M.end()) ans += (long long)it->second;
    }
    for (auto x : vec[i]) M[x.up]++;
  }
  for (int i = side[now]; i; i = nxt[i])
    if (!vis[toit[i]]) cut(find_root(toit[i], size[toit[i]]));
}
int main() {
  N = gi();
  lhh = gi();
  large[0] = inf;
  _10[0] = 1;
  for (int i = 1; i < maxn; ++i) _10[i] = _10[i - 1] * 10 % lhh;
  inv[maxn - 1] = exgcd(_10[maxn - 1], lhh, 1);
  for (int i = maxn - 1; i; --i) inv[i - 1] = inv[i] * 10 % lhh;
  for (int i = 1, a, b; i < N; ++i) a = gi() + 1, b = gi() + 1, ins(a, b, gi());
  cut(find_root(1, N));
  cout << ans << endl;
  return 0;
}
