#include <bits/stdc++.h>
using namespace std;
int n, m, phi;
vector<pair<int, int> > E[100005];
int mul(int a, int b) { return (int)(((long long)a * b) % m); }
int add(int a, int b) {
  a += b;
  if (a >= m) return a - m;
  return a;
}
int pot(int a, int first) {
  int r = 1;
  while (first) {
    if (first & 1) r = mul(r, a);
    a = mul(a, a), first >>= 1;
  }
  return r;
}
int inv(int a) { return pot(a, phi - 1); }
long long sol = 0;
bool forbidden[100005];
int sz[100005];
int maks[100005];
vector<int> all;
int dfs(int id, int p) {
  all.push_back(id);
  sz[id] = 1;
  maks[id] = -1;
  for (auto t : E[id])
    if (t.first != p && !forbidden[t.first]) {
      sz[id] += dfs(t.first, id);
      maks[id] = max(maks[id], sz[t.first]);
    }
  return sz[id];
}
void grupa(int id, int p, int a, int b, vector<pair<int, int> > &out) {
  out.push_back({a, b});
  for (auto t : E[id])
    if (t.first != p && !forbidden[t.first])
      grupa(t.first, id, mul(10, a), add(b, mul(a, t.second)), out);
}
void grupa2(int id, int p, int a, int b, vector<pair<int, int> > &out) {
  out.push_back({a, b});
  for (auto t : E[id])
    if (t.first != p && !forbidden[t.first])
      grupa2(t.first, id, mul(10, a), add(t.second, mul(10, b)), out);
}
void solve(int root) {
  vector<vector<pair<int, int> > > Vall = {{{1, 0}}};
  vector<vector<pair<int, int> > > Vall2 = {{{1, 0}}};
  for (auto t : E[root])
    if (!forbidden[t.first]) {
      Vall.push_back(vector<pair<int, int> >());
      grupa(t.first, root, 10 % m, t.second, Vall.back());
      Vall2.push_back(vector<pair<int, int> >());
      grupa2(t.first, root, 10 % m, t.second, Vall2.back());
    }
  bool d = false;
  if (d)
    cerr << "sol"
         << " = " << sol << endl;
  if (d)
    for (auto V : Vall) {
      for (auto Vt : V)
        cerr << "Vt.x _ Vt.y"
             << " = " << Vt.first << " _ " << Vt.second << endl;
      cout << endl;
    }
  map<int, int> M;
  for (auto V : Vall2)
    for (auto t : V) ++M[mul(m - t.second, inv(t.first))];
  if (d)
    for (auto Mt : M)
      cerr << "Mt.x _ Mt.y"
           << " = " << Mt.first << " _ " << Mt.second << endl;
  for (auto V : Vall)
    for (auto t : V) sol += M[t.second];
  if (d)
    cerr << "sol"
         << " = " << sol << endl;
  int tmp = 0;
  for (auto V : Vall) {
    M.clear();
    for (auto t : Vall2[tmp]) ++M[mul(m - t.second, inv(t.first))];
    for (auto t : V) sol -= M[t.second];
    ++tmp;
  }
  if (d)
    cerr << "sol"
         << " = " << sol << endl;
}
void centroid(int node, int debug = 0) {
  all.clear();
  dfs(node, node);
  if (sz[node] == 1) return;
  for (auto t : all) maks[t] = max(maks[t], sz[node] - sz[t]);
  int best = node;
  for (auto t : all)
    if (maks[t] < maks[best]) best = t;
  solve(best);
  forbidden[best] = true;
  for (auto t : E[best])
    if (!forbidden[t.first]) centroid(t.first, debug + 1);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = (int)(0); i < (int)(n - 1); ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    w %= m;
    E[u].push_back({v, w});
    E[v].push_back({u, w});
  }
  {
    int tmp = m;
    phi = 1;
    for (int i = 2; i * i <= tmp; ++i)
      if (tmp % i == 0) {
        phi *= i - 1;
        tmp /= i;
        while (tmp % i == 0) tmp /= i, phi *= i;
      }
    if (tmp != 1) phi *= tmp - 1;
  }
  centroid(0);
  cout << sol << endl;
  return 0;
}
