#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3fffffff;
const long long mod = 1000000007;
const int maxn = 100000 + 100;
long long fact[maxn], inv[maxn];
int n;
long long m;
int sz[maxn], mx[maxn];
int vis[maxn];
int root, mi;
long long ans;
map<int, int> mp;
bool flag;
long long ex_gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0 && b == 0) return -1;
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = ex_gcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
long long mod_inverse(long long a, long long n) {
  long long x, y;
  long long d = ex_gcd(a, n, x, y);
  return (x % n + n) % n;
}
void init() {
  fact[0] = 1;
  inv[0] = 1;
  for (int i = 1; i <= 100000; i++) {
    fact[i] = fact[i - 1] * 10ll % m;
    inv[i] = mod_inverse(fact[i], m);
  }
}
vector<pair<int, int> > G[maxn];
void dfssize(int u, int f) {
  sz[u] = 1, mx[u] = 0;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i].first;
    if (vis[v] || v == f) continue;
    dfssize(v, u);
    sz[u] += sz[v];
    if (sz[v] > mx[u]) mx[u] = sz[v];
  }
}
void dfsroot(int r, int u, int f) {
  if (sz[r] - sz[u] > mx[u]) mx[u] = sz[r] - sz[u];
  if (mx[u] < mi) mi = mx[u], root = u;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i].first;
    if (v == f || vis[v]) continue;
    dfsroot(r, v, u);
  }
}
void dfs1(int u, int f, int dep, int st) {
  if (!st && flag) ans++;
  int p = (m - st) * inv[dep] % m;
  ans += mp[p];
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i].first, w = G[u][i].second;
    if (vis[v] || v == f) continue;
    dfs1(v, u, dep + 1, (st * 10ll + w) % m);
  }
}
void dfs2(int u, int f, int dep, int st) {
  if (!st && flag) ans++;
  mp[st]++;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i].first, w = G[u][i].second;
    if (vis[v] || v == f) continue;
    dfs2(v, u, dep + 1, (1ll * w * fact[dep] + st) % m);
  }
}
void cal(int u) {
  mp.clear();
  flag = true;
  for (int i = 0; i < G[u].size(); i++) {
    int v = G[u][i].first, w = G[u][i].second;
    if (!vis[v]) {
      dfs1(v, u, 1, w % m);
      dfs2(v, u, 1, w % m);
    }
  }
  mp.clear();
  flag = false;
  for (int i = G[u].size() - 1; i >= 0; i--) {
    int v = G[u][i].first, w = G[u][i].second;
    if (!vis[v]) {
      dfs1(v, u, 1, w % m);
      dfs2(v, u, 1, w % m);
    }
  }
}
void dfs(int u) {
  mi = inf;
  dfssize(u, -1);
  dfsroot(u, u, -1);
  cal(root);
  vis[root] = 1;
  int p = root;
  for (int i = 0; i < G[p].size(); i++) {
    int v = G[p][i].first;
    if (vis[v]) continue;
    dfs(v);
  }
}
int main() {
  scanf("%d%I64d", &n, &m);
  init();
  for (int i = 1; i < n; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u++, v++;
    G[u].push_back(make_pair(v, w)), G[v].push_back(make_pair(u, w));
  }
  ans = 0;
  memset(vis, 0, sizeof(vis));
  dfs(1);
  printf("%I64d\n", ans);
  return 0;
}
