#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
inline void RI(int &x) {
  char c;
  while ((c = getchar()) < '0' || c > '9')
    ;
  x = c - '0';
  while ((c = getchar()) >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0';
}
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double dnf = 1e18;
const double eps = 1e-12;
const long long mod = 10007;
const int maxn = 100010;
struct Side {
  int to, next;
  long long w;
} side[maxn << 1];
int n, m;
int top, node[maxn];
bool del[maxn];
long long ans, f[maxn], inv[maxn];
void add_side(int u, int v, long long w) {
  side[top] = (Side){v, node[u], w};
  node[u] = top++;
}
void gcd(int a, int b, int &d, int &x, int &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    gcd(b, a % b, d, y, x);
    y -= x * (a / b);
  }
}
int get_inv(int a, int n) {
  int d, x, y;
  gcd(a, n, d, x, y);
  return d == 1 ? (x + n) % n : -1;
}
int total_size, size[maxn], max_size, idx, new_root;
map<int, int> sub[maxn], all;
vector<pair<int, int> > vv[maxn];
void get_size(int u, int pre) {
  size[u] = 1;
  for (int i = node[u]; i != -1; i = side[i].next) {
    int v = side[i].to;
    if (del[v] || v == pre) continue;
    get_size(v, u);
    size[u] += size[v];
  }
}
void dfs_root(int u, int pre) {
  int mx = 0, sum = 1;
  for (int i = node[u]; i != -1; i = side[i].next) {
    int v = side[i].to;
    if (del[v] || v == pre) continue;
    dfs_root(v, u);
    mx = max(mx, size[v]);
    sum += size[v];
  }
  mx = max(mx, total_size - sum);
  if (mx < max_size) max_size = mx, new_root = u;
}
int get_root(int root) {
  new_root = -1;
  max_size = (1 << 30);
  get_size(root, -1);
  total_size = size[root];
  dfs_root(root, -1);
  return new_root;
}
void get_deep1(int u, int pre, int deep, long long w) {
  sub[idx][w]++;
  for (int i = node[u]; i != -1; i = side[i].next) {
    int v = side[i].to;
    if (v == pre || del[v]) continue;
    long long ss = (w + f[deep] * side[i].w) % m;
    get_deep1(v, u, deep + 1, ss);
  }
}
void get_deep2(int u, int pre, int deep, long long w) {
  vv[idx].push_back(make_pair(deep, w));
  for (int i = node[u]; i != -1; i = side[i].next) {
    int v = side[i].to;
    if (v == pre || del[v]) continue;
    get_deep2(v, u, deep + 1, (w * 10 + side[i].w) % m);
  }
}
long long get_ans(vector<pair<int, int> > a, map<int, int> mp) {
  long long ans = 0;
  for (int i = 0; i < a.size(); i++) {
    long long t = (m - a[i].second) * inv[a[i].first] % m;
    if (mp.count(t)) ans += mp[t];
  }
  return ans;
}
void solve(int root) {
  root = get_root(root);
  del[root] = 1;
  if (total_size == 1) return;
  idx = 0;
  sub[idx].clear();
  sub[idx++][0] = 1;
  all.clear();
  all[0] = 1;
  for (int i = node[root]; i != -1; i = side[i].next) {
    int v = side[i].to;
    if (del[v]) continue;
    sub[idx].clear();
    get_deep1(v, root, 1, side[i].w % m);
    for (map<int, int>::iterator it = sub[idx].begin(); it != sub[idx].end();
         it++)
      all[it->first] += it->second;
    idx++;
  }
  idx = 0;
  vv[idx].clear();
  vv[idx++].push_back(make_pair(0, 0));
  for (int i = node[root]; i != -1; i = side[i].next) {
    int v = side[i].to;
    if (del[v]) continue;
    vv[idx].clear();
    get_deep2(v, root, 1, side[i].w % m);
    idx++;
  }
  for (int i = 0; i < idx; i++)
    ans += get_ans(vv[i], all) - get_ans(vv[i], sub[i]);
  for (int i = node[root]; i != -1; i = side[i].next) {
    int v = side[i].to;
    if (del[v]) continue;
    solve(v);
  }
}
int main() {
  while (cin >> n >> m) {
    inv[0] = f[0] = 1;
    for (int i = 1; i < maxn; i++) {
      f[i] = f[i - 1] * 10 % m;
      inv[i] = get_inv(f[i], m);
    }
    top = 0;
    memset(node, -1, sizeof(node));
    for (int i = 0; i < n - 1; i++) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      add_side(u, v, w);
      add_side(v, u, w);
    }
    memset(del, 0, sizeof(del));
    ans = 0;
    solve(0);
    cout << ans << endl;
  }
}
