#include <bits/stdc++.h>
using namespace std;
struct CentroidD {
  long long n, val_vis;
  vector<vector<long long> > adj, pes;
  vector<long long> cparent, szt, vis;
  vector<vector<long long> > cdTree;
  CentroidD(){};
  CentroidD(long long n) : n(n) {
    val_vis = 0;
    vis.resize(n, -1);
    cparent.resize(n, -1);
    szt.resize(n, 0);
    adj.resize(n);
    pes.resize(n);
    cdTree.resize(n);
  }
  void addEdge(long long u, long long v, long long w) {
    adj[u].push_back(v);
    adj[v].push_back(u);
    pes[u].push_back(w);
    pes[v].push_back(w);
    return;
  }
  long long dfs(long long u, long long p) {
    szt[u] = 1;
    vis[u] = val_vis;
    for (long long v : adj[u]) {
      if (v != p && cparent[v] == -1 && vis[v] != val_vis) szt[u] += dfs(v, u);
    }
    return szt[u];
  }
  void decompotition(long long u, long long p, long long sz, long long pc) {
    for (long long v : adj[u]) {
      if (v != p && cparent[v] == -1 && (szt[v] << 1ll) > sz) {
        decompotition(v, u, sz, pc);
        return;
      }
    }
    cparent[u] = pc;
    if (pc != -2) {
      cdTree[u].push_back(pc);
      cdTree[pc].push_back(u);
    }
    for (long long v : adj[u]) {
      if (cparent[v] == -1) {
        dfs(v, -1);
        val_vis++;
        decompotition(v, -1, szt[v], u);
      }
    }
  }
  void build(long long u) {
    dfs(u, -1);
    val_vis++;
    decompotition(u, -1, szt[u], -2);
  }
};
const long long MX = 1e5 + 10;
CentroidD G;
vector<pair<long long, long long> > lc;
vector<pair<long long, long long> > cl;
bool visCentroid[MX];
long long pot[MX];
long long ans, MOD;
long long inverse(long long a, long long m) {
  long long m0 = m;
  long long y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m;
    a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) {
    x += m0;
  }
  return x;
}
void getVector(long long u, long long p, long long w_lc, long long w_cl,
               long long d) {
  for (long long i = 0; i < G.adj[u].size(); i++) {
    long long v = G.adj[u][i];
    long long w = G.pes[u][i];
    if (v != p && !visCentroid[v]) {
      getVector(v, u, (w * pot[d] + w_lc) % MOD, (w_cl * 10 + w) % MOD, d + 1);
    }
  }
  lc.push_back({w_lc, d});
  cl.push_back({w_cl, d});
  return;
}
void calculate(long long u) {
  vector<vector<pair<long long, long long> > > leaf_cent, cent_leaf;
  for (long long i = 0; i < G.adj[u].size(); i++) {
    long long v = G.adj[u][i];
    long long w = G.pes[u][i];
    if (!visCentroid[v]) {
      lc.clear();
      cl.clear();
      getVector(v, u, w, w, 1);
      leaf_cent.push_back(lc);
      cent_leaf.push_back(cl);
    }
  }
  for (long long i = 0; i < cent_leaf.size(); i++) {
    for (long long j = 0; j < cent_leaf[i].size(); j++) {
      if (cent_leaf[i][j].first % MOD == 0) ans++;
    }
  }
  for (long long i = 0; i < leaf_cent.size(); i++) {
    for (long long j = 0; j < leaf_cent[i].size(); j++) {
      if (leaf_cent[i][j].first % MOD == 0) ans++;
    }
  }
  map<long long, long long> cnt;
  for (long long i = 0; i < cent_leaf.size(); i++) {
    for (long long j = 0; j < cent_leaf[i].size(); j++) {
      long long num = (MOD - cent_leaf[i][j].first) % MOD;
      long long den = pot[cent_leaf[i][j].second];
      cnt[(num * inverse(den, MOD)) % MOD]++;
    }
  }
  for (long long i = 0; i < leaf_cent.size(); i++) {
    vector<long long> aux;
    for (long long j = 0; j < cent_leaf[i].size(); j++) {
      long long num = (MOD - cent_leaf[i][j].first) % MOD;
      long long den = pot[cent_leaf[i][j].second];
      long long rp = (num * inverse(den, MOD)) % MOD;
      aux.push_back(rp);
      cnt[rp]--;
    }
    for (long long j = 0; j < leaf_cent[i].size(); j++) {
      ans += cnt[leaf_cent[i][j].first];
    }
    for (long long xx : aux) cnt[xx]++;
  }
  return;
}
void dfs(long long u, long long p) {
  visCentroid[u] = true;
  calculate(u);
  for (long long v : G.cdTree[u]) {
    if (v != p) dfs(v, u);
  }
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout.precision(10);
  cout << fixed;
  long long n, x, y, w;
  cin >> n >> MOD;
  G = CentroidD(n);
  for (long long i = 1; i < n; i++) {
    cin >> x >> y >> w;
    G.addEdge(x, y, w % MOD);
  }
  G.build(0);
  long long centroid = -1;
  for (long long i = 0; i < n; i++) {
    if (G.cparent[i] == -2) centroid = i;
  }
  pot[0] = 1 % MOD;
  for (long long i = 1; i < MX; i++) pot[i] = (pot[i - 1] * 10) % MOD;
  ans = 0;
  dfs(centroid, -1);
  cout << ans << "\n";
  return 0;
}
