#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = 0x7fffffff;
void gcd(long long a, long long b, long long d, long long &x, long long &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    gcd(b, a % b, d, y, x);
    y -= x * (a / b);
  }
}
struct Edge {
  int to, d;
  Edge() {}
  Edge(int to, int d) : to(to), d(d) {}
};
vector<Edge> V[N];
int n, sz[N];
long long ans, K, K1[N], F[N];
bool mk[N];
long long cal_rev(long long a) {
  long long d, x, y;
  gcd(a, K, d, x, y);
  return (x + K) % K;
}
void dfs1(int x, int fa) {
  sz[x] = 1;
  for (int i = 0; i < V[x].size(); i++) {
    int j = V[x][i].to;
    if (j == fa || mk[j]) continue;
    dfs1(j, x);
    sz[x] = sz[x] + sz[j];
  }
}
pair<int, int> dfs2(int x, int fa, int sum) {
  pair<int, int> ret = make_pair(inf, inf);
  int m = 0;
  for (int i = 0; i < V[x].size(); i++) {
    int j = V[x][i].to;
    if (j == fa || mk[j]) continue;
    ret = min(ret, dfs2(j, x, sum));
    m = max(m, sz[j]);
  }
  m = max(m, sum - sz[x]);
  return min(ret, make_pair(m, x));
}
long long O[N], P[N], Q[N], R[N];
int o_len, p_len, q_len, r_len;
void get_path(int x, int fa, int dep, long long cur1, long long cur2) {
  long long v = (K - cur2) % K * K1[dep] % K;
  Q[q_len++] = cur1;
  R[r_len++] = v;
  long long v1, v2;
  if (cur1 == 0) {
    ans = ans + 1;
  }
  if (cur2 == 0) {
    ans = ans + 1;
  }
  for (int i = 0; i < V[x].size(); i++) {
    int j = V[x][i].to;
    if (j == fa || mk[j]) continue;
    v1 = F[dep] * V[x][i].d + cur1;
    v2 = cur2 * 10 + V[x][i].d;
    if (v1 >= K) {
      v1 = v1 % K;
    }
    if (v2 >= K) {
      v2 = v2 % K;
    }
    get_path(j, x, dep + 1, v1, v2);
  }
}
long long Count(long long *A, int n, long long *B, int m) {
  sort(A, A + n);
  sort(B, B + m);
  long long ret = 0;
  int j = 0, pre = -1, cnt = 0;
  for (int i = 0; i < m; i++) {
    if (B[i] == pre) {
      ret = ret + cnt;
      continue;
    }
    while (j < n && A[j] < B[i]) {
      j++;
    }
    cnt = 0;
    while (j < n && A[j] == B[i]) {
      j++;
      cnt++;
    }
    ret = ret + cnt;
    pre = B[i];
  }
  return ret;
}
void doit(int x) {
  dfs1(x, -1);
  int s = dfs2(x, -1, sz[x]).second;
  mk[s] = 1;
  for (int i = 0; i < V[s].size(); i++) {
    int j = V[s][i].to;
    if (!mk[j]) {
      doit(j);
    }
  }
  o_len = p_len = 0;
  for (int i = 0; i < V[s].size(); i++) {
    int j = V[s][i].to;
    if (!mk[j]) {
      q_len = r_len = 0;
      get_path(j, s, 1, V[s][i].d % K, V[s][i].d % K);
      for (int i = 0; i < q_len; i++) {
        O[o_len++] = Q[i];
      }
      for (int i = 0; i < r_len; i++) {
        P[p_len++] = R[i];
      }
      ans = ans - Count(Q, q_len, R, r_len);
    }
  }
  ans = ans + Count(O, o_len, P, p_len);
  mk[s] = 0;
}
long long solve() {
  ans = 0;
  doit(0);
  return ans;
}
int main() {
  int x, y, d;
  while (~scanf("%d %I64d", &n, &K)) {
    K1[0] = 1;
    F[0] = 1;
    for (int i = 1; i <= n; i++) {
      F[i] = F[i - 1] * 10 % K;
      K1[i] = cal_rev(F[i]);
    }
    for (int i = 0; i < n; i++) {
      V[i].clear();
      mk[i] = 0;
    }
    for (int i = 1; i < n; i++) {
      scanf("%d %d %d", &x, &y, &d);
      V[x].push_back(Edge(y, d));
      V[y].push_back(Edge(x, d));
    }
    printf("%I64d\n", solve());
  }
  return 0;
}
