#include <bits/stdc++.h>
using namespace std;
template <typename number_t>
inline void make_positive(number_t& a, const number_t mod) {
  a = ((a % mod) + mod) % mod;
}
template <typename number_t>
inline number_t modulo_inverse(number_t a, const number_t mod) {
  make_positive<number_t>(a, mod);
  number_t b = mod, ret = 1, rem = 0;
  while (1 < a) {
    const auto old_b = b, quotient = a / b;
    b = a % b;
    a = old_b;
    const auto old_remainder = rem;
    rem = ret - (quotient * rem);
    ret = old_remainder;
  }
  make_positive<number_t>(ret, mod);
  return ret;
}
long long ans, mod, one_tenth;
constexpr int MAX_N = 100 * 1024;
vector<pair<int, int>> adj_list[MAX_N];
vector<int> vertex_visit_orders;
int sizes[MAX_N];
bool centers[MAX_N];
int center_tmp;
int down_values[MAX_N], up_values[MAX_N], heights_rev[MAX_N];
int components[MAX_N], components_cnt;
map<int, int> up_map_all;
map<int, int> up_map_subtree[MAX_N];
void dfs(const int root, const int parent = -1) {
  sizes[root] = 1;
  for (const auto& p : adj_list[root]) {
    const auto& v = p.first;
    if (parent != v && !centers[v]) {
      dfs(v, root);
      sizes[root] += sizes[v];
    }
  }
}
int find_tree_center(int root) {
  int parent = -1;
  const auto half_size = sizes[root] >> 1;
  for (;;) {
    auto is_center = true;
    for (const auto& p : adj_list[root]) {
      const auto& v = p.first;
      if (parent != v && !centers[v] && half_size < sizes[v]) {
        is_center = false;
        parent = root;
        root = v;
        break;
      }
    }
    if (is_center) return root;
  }
}
void dfs2_calc(const int root, const int parent = -1, const int height = 1,
               const int height_rev = 1) {
  if (center_tmp == parent)
    components[root] = ++components_cnt;
  else if (0 <= parent)
    components[root] = components[parent];
  vertex_visit_orders.push_back(root);
  up_map_all[up_values[root]]++;
  up_map_subtree[components[root]][up_values[root]]++;
  const auto down = static_cast<int>((down_values[root] * 10ll) % mod),
             h2 = static_cast<int>((height * 10ll) % mod),
             h2_rev = static_cast<int>((one_tenth * height_rev) % mod);
  for (const auto& p : adj_list[root]) {
    const auto& v = p.first;
    if (parent != v && !centers[v]) {
      down_values[v] = (down + p.second) % mod;
      up_values[v] =
          (static_cast<long long>(height) * p.second + up_values[root]) % mod;
      heights_rev[v] = h2_rev;
      dfs2_calc(v, root, h2, h2_rev);
    }
  }
}
void visit_center() {
  centers[center_tmp] = true;
  if (sizes[center_tmp] <= 1) return;
  down_values[center_tmp] = up_values[center_tmp] = heights_rev[center_tmp] =
      components[center_tmp] = 0;
  components_cnt = 0;
  {
    up_map_all.clear();
    const auto si = static_cast<int>(adj_list[center_tmp].size());
    for (int i = 0; i <= si; i++) up_map_subtree[i].clear();
  }
  dfs2_calc(center_tmp);
  for (const auto& v : vertex_visit_orders) {
    const auto other_subtree_up =
        static_cast<int>(((mod - down_values[v]) * heights_rev[v]) % mod);
    ans += up_map_all[other_subtree_up] -
           up_map_subtree[components[v]][other_subtree_up];
  }
  vertex_visit_orders.clear();
}
void visit_all_tree_centers(const int root) {
  dfs(root);
  const auto c1 = center_tmp = find_tree_center(root);
  visit_center();
  for (const auto& p : adj_list[c1]) {
    const auto& v = p.first;
    if (!centers[v]) visit_all_tree_centers(v);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  bool st = false;
  while (cin >> n >> mod) {
    if (st) {
      ans = 0;
      for (int i = 0; i <= n; i++) adj_list[i].clear();
      memset(centers, 0, sizeof centers);
    } else
      st = true;
    for (int i = 1; i < n; i++) {
      int u, v, weight;
      cin >> u >> v >> weight;
      weight = weight % mod;
      adj_list[u].push_back(make_pair(v, weight));
      adj_list[v].push_back(make_pair(u, weight));
    }
    if (1 == mod) {
      cout << n * (n - 1ll) << '\n';
      continue;
    }
    one_tenth = modulo_inverse(10ll, mod);
    visit_all_tree_centers(0);
    cout << ans << '\n';
  }
  return 0;
}
