#include <bits/stdc++.h>
using namespace std;
int n, m, root, sum;
int tot, point[100005], nxt[100005 * 2], v[100005 * 2], c[100005 * 2];
long long ans;
int mi[100005], big[100005], size[100005], pt[100005], deep[100005],
    numup[100005], numdown[100005];
bool vis[100005];
map<int, int> cntup;
void add(int x, int y, int z) {
  ++tot;
  nxt[tot] = point[x];
  point[x] = tot;
  v[tot] = y;
  c[tot] = z;
}
void getroot(int x, int fa) {
  size[x] = 1;
  big[x] = 0;
  for (int i = point[x]; i; i = nxt[i])
    if (v[i] != fa && !vis[v[i]]) {
      getroot(v[i], x);
      size[x] += size[v[i]];
      big[x] = max(big[x], size[v[i]]);
    }
  big[x] = max(big[x], sum - size[x]);
  if (big[root] > big[x]) root = x;
}
void getdeep(int x, int fa, int dep) {
  pt[++pt[0]] = x;
  deep[x] = dep;
  ++cntup[numup[x]];
  for (int i = point[x]; i; i = nxt[i])
    if (v[i] != fa && !vis[v[i]]) {
      numup[v[i]] = (numup[x] + (long long)c[i] * mi[dep] % m) % m;
      numdown[v[i]] = ((long long)numdown[x] * 10 % m + c[i]) % m;
      getdeep(v[i], x, dep + 1);
    }
}
int gcd(int a, int b) {
  if (!b)
    return a;
  else
    return gcd(b, a % b);
}
void exgcd(int a, int b, int &x, int &y) {
  if (!b)
    x = 1, y = 0;
  else
    exgcd(b, a % b, y, x), y -= a / b * x;
}
int tongyu(int a, int b, int m) {
  int t = gcd(a, m);
  if (b % t) return -1;
  a /= t, m /= t, b /= t;
  int x = 0, y = 0;
  exgcd(a, m, x, y);
  x = (((long long)b * x) % m + m) % m;
  return x;
}
long long calc(int x, int now) {
  numup[x] = now % m;
  numdown[x] = now % m;
  pt[0] = 0;
  cntup.clear();
  getdeep(x, 0, (now) ? 1 : 0);
  long long t = 0;
  for (int i = 1; i <= pt[0]; ++i) {
    int b = (-numdown[pt[i]] % m + m) % m;
    int a = mi[deep[pt[i]]];
    int state = tongyu(a, b, m);
    if (state == -1) continue;
    t += (long long)cntup[state];
  }
  if (!now) --t;
  return t;
}
void dfs(int x) {
  ans += calc(x, 0);
  vis[x] = 1;
  for (int i = point[x]; i; i = nxt[i])
    if (!vis[v[i]]) {
      ans -= calc(v[i], c[i]);
      root = 0;
      sum = size[v[i]];
      getroot(v[i], 0);
      dfs(root);
    }
}
int main() {
  scanf("%d%d", &n, &m);
  mi[0] = 1;
  for (int i = 1; i <= n; ++i) mi[i] = (long long)mi[i - 1] * 10 % m;
  for (int i = 1; i < n; ++i) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    ++x, ++y;
    add(x, y, z), add(y, x, z);
  }
  big[0] = 100005;
  root = 0;
  sum = n;
  getroot(1, 0);
  dfs(root);
  printf("%I64d\n", ans);
}
