#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 7;
int n, mod;
inline int add(long long x, long long y) { return (x % mod + y % mod) % mod; }
inline int mul(long long x, long long y) { return (x % mod * y % mod) % mod; }
inline int fpow(long long x, long long y) {
  int res = 1;
  while (y) {
    if (y & 1) res = mul(res, x);
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}
inline int totient(long long x) {
  long long res = x;
  for (long long i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      res = res * (i - 1) / i;
      while (x % i == 0) x /= i;
    }
  }
  if (x > 1) res = res * (x - 1) / x;
  return res;
}
long long pwr10[MAX];
long long inv_pwr10[MAX];
set<pair<int, int>> adj[MAX];
int sz[MAX];
int get_sz(int node, int par) {
  sz[node] = 1;
  for (pair<int, int> to : adj[node])
    if (to.first != par) sz[node] += get_sz(to.first, node);
  return sz[node];
}
int centroid(int node, int par, int n) {
  for (pair<int, int> to : adj[node])
    if (to.first != par && sz[to.first] > n / 2)
      return centroid(to.first, node, n);
  return node;
}
static long long ANS = 0;
long long get(vector<pair<int, pair<int, int>>> vec) {
  map<int, int> memo;
  for (pair<int, pair<int, int>> x : vec) memo[x.second.second]++;
  long long res = 0;
  for (pair<int, pair<int, int>> x : vec) {
    long long tmp = mul(x.second.first, inv_pwr10[x.first]);
    if (memo.count((mod - tmp) % mod)) res += memo[(mod - tmp) % mod];
  }
  return res;
}
vector<pair<int, pair<int, int>>> vec;
void dfs(int node, int par, int depth, int inmod, int outmod) {
  vec.push_back({depth, {inmod, outmod}});
  for (pair<int, int> to : adj[node])
    if (to.first != par)
      dfs(to.first, node, depth + 1, add(to.second, mul(inmod, 10)),
          add(outmod, mul(to.second, pwr10[depth])));
}
void solve(int node, int par) {
  int n = get_sz(node, par);
  int c = centroid(node, par, n);
  set<pair<int, int>> edges = adj[c];
  if (n == 1) return;
  vector<pair<int, pair<int, int>>> all;
  for (pair<int, int> x : edges) {
    vec.clear();
    dfs(x.first, c, 1, x.second % mod, x.second % mod);
    for (pair<int, pair<int, int>> x : vec)
      ANS += x.second.first == 0, ANS += x.second.second == 0;
    ANS -= get(vec);
    for (auto x : vec) all.push_back(x);
  }
  ANS += get(all);
  for (pair<int, int> x : edges) {
    adj[c].erase(x);
    adj[x.first].erase({c, x.second});
    solve(x.first, par);
  }
}
int main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> mod;
  for (int i = 0; i < n - 1; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].insert({v, w});
    adj[v].insert({u, w});
  }
  pwr10[0] = 1;
  for (int i = 1; i < MAX; ++i) pwr10[i] = mul(pwr10[i - 1], 10);
  inv_pwr10[MAX - 1] = fpow(pwr10[MAX - 1], totient(mod) - 1);
  for (int i = MAX - 2; i >= 0; --i) inv_pwr10[i] = mul(inv_pwr10[i + 1], 10);
  if (mod == 1)
    cout << 1LL * n * (n - 1) << '\n';
  else
    solve(0, -1), cout << ANS << '\n';
  return 0;
}
