#include <bits/stdc++.h>
using namespace std;
int head[100005], nxt[100005 << 1], to[100005 << 1], v[100005 << 1], tot;
int mx[100005], sz[100005], root, sum, num;
int A[100005], n, P;
bool mk[100005];
long long ans;
map<int, long long> mp;
struct node {
  int d, dep;
} Ans[100005];
inline void Max(int &x, int y) {
  if (y > x) x = y;
}
inline void Add(int x, int y, int z) {
  nxt[++tot] = head[x];
  head[x] = tot;
  to[tot] = y;
  v[tot] = z;
}
void getrt(int x, int f) {
  sz[x] = 1, mx[x] = 0;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = to[i];
    if (y != f && !mk[y]) {
      getrt(y, x);
      sz[x] += sz[y];
      Max(mx[x], sz[y]);
    }
  }
  Max(mx[x], sum - sz[x]);
  if (mx[root] > mx[x]) root = x;
}
void exgcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= x * (a / b);
}
int Inv(int a, int b) {
  int x, y;
  exgcd(a, b, x, y);
  return (x % b + b) % b;
}
void dfs(int x, int f, int d1, int d2, int dep) {
  if (dep >= 0) {
    mp[d1]++;
    Ans[++num] = (node){d2, dep};
  }
  for (int i = head[x]; i; i = nxt[i]) {
    int y = to[i];
    if ((y != f) && (!mk[y])) {
      int d3 = (d1 + 1LL * v[i] * A[dep + 1] % P) % P;
      int d4 = (1LL * d2 * 10 % P + v[i]) % P;
      dfs(y, x, d3, d4, dep + 1);
    }
  }
}
long long Cal(int x, int d) {
  long long res = 0;
  mp.clear();
  num = 0;
  if (d)
    dfs(x, 0, d % P, d % P, 0);
  else
    dfs(x, 0, 0, 0, -1);
  for (int i = (1), i_ = (num); i <= i_; i++) {
    int tmp = (-1LL * Ans[i].d * Inv(A[Ans[i].dep + 1], P) % P + P) % P;
    if (mp.find(tmp) != mp.end()) res += mp[tmp];
    if (!d) res += (Ans[i].d == 0);
  }
  if (!d) res += mp[0];
  return res;
}
void Solve(int rt) {
  ans += Cal(rt, 0);
  mk[rt] = 1;
  for (int i = head[rt]; i; i = nxt[i]) {
    int y = to[i];
    if (!mk[y]) {
      ans -= Cal(y, v[i]);
      sum = sz[y], root = 0;
      getrt(y, 0);
      Solve(root);
    }
  }
}
int main() {
  int a, b, c;
  scanf("%d%d", &n, &P);
  A[0] = 1;
  for (int i = (1), i_ = (n); i <= i_; i++) A[i] = 1LL * A[i - 1] * 10 % P;
  for (int i = (1), i_ = (n - 1); i <= i_; i++) {
    scanf("%d%d%d", &a, &b, &c);
    a++, b++;
    Add(a, b, c), Add(b, a, c);
  }
  sum = n, root = 0;
  mx[0] = 1e9;
  getrt(1, 0);
  Solve(root);
  printf("%lld\n", ans);
  return 0;
}
