#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
int N, M, PHI;
int tree_size, centroid_root;
int sz[MAX], centroid_parent[MAX], height[MAX];
bool computed[MAX];
vector<int> centroid_tree[MAX];
vector<pair<int, int> > adj[MAX];
long long pot[MAX], up[MAX], down[MAX];
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long x1, y1;
  long long d = ext_gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - y1 * (a / b);
  return d;
}
long long inv(long long k) {
  long long x, y;
  ext_gcd(k, M, x, y);
  return x;
}
int calc_size(int source, int father) {
  sz[source] = 1;
  tree_size++;
  for (auto &each : adj[source]) {
    if (!computed[each.first] && each.first != father) {
      sz[source] += calc_size(each.first, source);
    }
  }
  return sz[source];
}
int find_centroid(int source, int father) {
  for (auto &each : adj[source]) {
    if (!computed[each.first] && each.first != father &&
        sz[each.first] > tree_size / 2) {
      return find_centroid(each.first, source);
    }
  }
  return source;
}
void build_centroid(int source, int last_centroid) {
  tree_size = 0;
  calc_size(source, -1);
  int centroid = find_centroid(source, -1);
  computed[centroid] = 1;
  centroid_parent[centroid] = last_centroid;
  if (last_centroid != -1) {
    centroid_tree[last_centroid].push_back(centroid);
  } else {
    centroid_root = centroid;
  }
  for (auto &each : adj[centroid]) {
    if (!computed[each.first]) {
      build_centroid(each.first, centroid);
    }
  }
}
map<long long, int> app;
map<long long, int> app_sub[MAX];
void prepare(int source, int father, int representative) {
  for (auto &each : adj[source]) {
    if (!computed[each.first] && each.first != father) {
      height[each.first] = height[source] + 1;
      up[each.first] =
          (pot[height[each.first] - 1] * each.second + up[source]) % M;
      down[each.first] = (down[source] * 10 + each.second) % M;
      app[up[each.first]]++;
      app_sub[representative][up[each.first]]++;
      prepare(each.first, source, representative);
    }
  }
}
void do_the_magic(int source, int father, int rep, long long &ans) {
  ans += up[source] == 0;
  ans += down[source] == 0;
  long long search = (-down[source] * inv(pot[height[source]])) % M;
  while (0 > search) {
    search += M;
  }
  ans += app[search];
  ans -= app_sub[rep][search];
  for (auto &each : adj[source]) {
    if (!computed[each.first] && each.first != father) {
      do_the_magic(each.first, source, rep, ans);
    }
  }
}
long long roll(int node) {
  app.clear();
  height[node] = up[node] = down[node] = 0;
  for (int i = int(0); i < int(adj[node].size()); i++) {
    app_sub[i].clear();
    auto each = adj[node][i];
    if (!computed[each.first]) {
      height[each.first] = 1;
      up[each.first] = down[each.first] = each.second % M;
      app[up[each.first]]++;
      app_sub[i][up[each.first]]++;
      prepare(each.first, node, i);
    }
  }
  computed[node] = true;
  long long ans = 0;
  for (int i = int(0); i < int(adj[node].size()); i++) {
    auto each = adj[node][i];
    if (!computed[each.first]) {
      do_the_magic(each.first, -1, i, ans);
    }
  }
  for (auto &each : centroid_tree[node]) {
    ans += roll(each);
  }
  return ans;
}
int main() {
  scanf("%d %d", &N, &M);
  pot[0] = 1;
  for (int i = int(1); i < int(MAX - 5 + 1); i++) {
    pot[i] = (pot[i - 1] * 10) % M;
  }
  for (int i = int(0); i < int(N - 1); i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  build_centroid(0, -1);
  memset(computed, false, sizeof computed);
  long long ans = roll(centroid_root);
  printf("%lld\n", ans);
  return 0;
}
