#include <bits/stdc++.h>
using namespace std;
template <typename T>
void mnm(T &a, T b) {
  a = min(a, b);
};
template <typename T>
void mxm(T &a, T b) {
  a = max(a, b);
};
template <typename T>
int discrete_id(vector<T> &vals, T val, int startId = 1) {
  return startId +
         (int)(lower_bound(vals.begin(), vals.end(), val) - vals.begin());
}
long long power(long long a, long long n, long long mod) {
  long long ans = 1;
  while (n) {
    if (n & 1) ans = (ans * a) % mod;
    a = (a * a) % mod;
    n /= 2;
  }
  return ans;
}
long long modul(long long x, long long mod) {
  x %= mod;
  if (x < 0) x += mod;
  return x;
}
tuple<long long, long long, long long> eea(long long x, long long y) {
  if (y == 0) return {1LL, 0LL, x};
  long long a, b, d, q = x / y;
  tie(a, b, d) = eea(y, x % y);
  return {b, a - b * q, d};
}
long long inv(long long x, long long m) {
  long long a, b, d;
  tie(a, b, d) = eea(x, m);
  assert(d == 1);
  return modul(a, m);
}
char i2c(int c) { return (char)(c + '0'); }
int get_subtree_sz(int u, int pa, vector<vector<pair<int, int>>> &adj,
                   vector<bool> &deleted, vector<int> &subsz) {
  subsz[u] = 1;
  for (auto e : adj[u]) {
    int v = e.first;
    if (v != pa && !deleted[v]) {
      subsz[u] += get_subtree_sz(v, u, adj, deleted, subsz);
    }
  }
  return subsz[u];
}
int get_centroid(int u, int pa, int desired,
                 vector<vector<pair<int, int>>> &adj, vector<bool> &deleted,
                 vector<int> &subsz) {
  for (auto e : adj[u]) {
    int v = e.first;
    if (v != pa && !deleted[v] && subsz[v] > desired) {
      return get_centroid(v, u, desired, adj, deleted, subsz);
    }
  }
  return u;
}
int neg(int u, int mod) { return (mod - u) % mod; }
void visit(int u, int pa, vector<vector<pair<int, int>>> &adj,
           vector<bool> &deleted, map<int, int> &need_up, map<int, int> &cnt_up,
           long long &ans, bool add, int _10pd, int _10pmd, int inv10,
           int cur_up, int cur_down, int m, int depth = 1) {
  if (add) {
    ans += cnt_up[(1LL * neg(cur_down, m) * _10pmd) % m];
    ans += need_up[cur_up];
  } else {
    ++cnt_up[cur_up];
    ++need_up[(1LL * neg(cur_down, m) * _10pmd) % m];
  }
  for (auto e : adj[u]) {
    int v, w;
    tie(v, w) = e;
    if (v != pa && !deleted[v]) {
      w %= m;
      int new_down = (10LL * cur_down + w) % m;
      int new_up = (1LL * w * _10pd + cur_up) % m;
      visit(v, u, adj, deleted, need_up, cnt_up, ans, add, (10LL * _10pd) % m,
            (1LL * inv10 * _10pmd) % m, inv10, new_up, new_down, m, depth + 1);
    }
  }
}
long long centroid_decomp(int u, vector<vector<pair<int, int>>> &adj,
                          vector<bool> &deleted, vector<int> &subsz,
                          map<int, int> &need_up, map<int, int> &cnt_up, int m,
                          int inv10) {
  u = get_centroid(u, 0, get_subtree_sz(u, 0, adj, deleted, subsz) / 2, adj,
                   deleted, subsz);
  deleted[u] = true;
  cnt_up[0] = 1;
  need_up[0] = 1;
  long long ans = 0;
  for (auto e : adj[u]) {
    int v, w;
    tie(v, w) = e;
    if (!deleted[v]) {
      w %= m;
      visit(v, u, adj, deleted, need_up, cnt_up, ans, true, 10 % m, inv10,
            inv10, w, w, m);
      visit(v, u, adj, deleted, need_up, cnt_up, ans, false, 10 % m, inv10,
            inv10, w, w, m);
    }
  }
  cnt_up.clear();
  need_up.clear();
  for (auto e : adj[u]) {
    int v = e.first;
    if (!deleted[v]) {
      long long tmp =
          centroid_decomp(v, adj, deleted, subsz, need_up, cnt_up, m, inv10);
      ans += tmp;
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> adj(n + 1);
  for (int i = (int)(1); i <= (int)(n - 1); ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
  }
  vector<bool> deleted(n + 1, 0);
  vector<int> subsz(n + 1);
  map<int, int> need_up, cnt_up;
  long long a, b, d;
  tie(a, b, d) = eea(10LL, m);
  int inv10 = modul(a, m);
  cout << centroid_decomp(0, adj, deleted, subsz, need_up, cnt_up, m, inv10)
       << "\n";
}
