#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
int t, n;
int MOD;
vector<pair<long long int, long long int> > v[N];
long long int kol[N];
long long int gotov[N], sad, a, b;
long long int c;
long long int sol;
vector<long long int> p;
long long int FI;
long long int inv[N], inv1[N];
long long int powmod(long long int a, long long int x) {
  long long int rez = 1;
  while (x) {
    if (x % 2) {
      rez = ((rez % MOD) * (a % MOD)) % MOD;
    }
    a = ((a % MOD) * (a % MOD)) % MOD;
    x /= 2;
  }
  return rez % MOD;
}
long long int divide(long long int a, long long int dub) {
  return a * inv[dub] % MOD;
}
int djeca(int node, int par) {
  kol[node] = 0;
  for (int i = 0; i < v[node].size(); i++) {
    if (v[node][i].first != par && !gotov[v[node][i].first])
      kol[node] += djeca(v[node][i].first, node);
  }
  kol[node]++;
  return kol[node];
}
int centr(int node, int par, int sz) {
  for (int i = 0; i < v[node].size(); i++) {
    if (v[node][i].first != par && !gotov[v[node][i].first] &&
        kol[v[node][i].first] > sz / 2) {
      return centr(v[node][i].first, node, sz);
    }
  }
  return node;
}
map<long long int, long long int> m;
map<long long int, long long int> pom[N];
void dfs(int node, int par, long long int x, long long int y, int d, int turn) {
  int di = ((-y) % MOD + MOD) % MOD;
  di = divide(di, d) % MOD;
  if (par != -1) sol += (m[di] - pom[turn][di]);
  if (!x && par != -1) sol++;
  if (!y && par != -1) sol++;
  for (int i = 0; i < v[node].size(); i++) {
    if (v[node][i].first != par && !gotov[v[node][i].first]) {
      int kamo;
      if (par == -1)
        kamo = i;
      else
        kamo = turn;
      long long int novix = ((v[node][i].second * inv1[d]) % MOD + x) % MOD;
      long long int noviy = ((y * 10) % MOD + v[node][i].second) % MOD;
      dfs(v[node][i].first, node, novix, noviy, d + 1, kamo);
      if (par == -1) pom[i].clear();
    }
  }
  return;
}
void broji(int node, int par, long long int x, int d, int turn) {
  if (par != -1) {
    m[x % MOD]++;
    pom[turn][x % MOD]++;
  }
  for (int i = 0; i < v[node].size(); i++) {
    if (v[node][i].first != par && !gotov[v[node][i].first]) {
      int kamo;
      if (par == -1)
        kamo = i;
      else
        kamo = turn;
      long long int novix = ((v[node][i].second * inv1[d]) % MOD + x) % MOD;
      broji(v[node][i].first, node, novix, d + 1, kamo);
    }
  }
  return;
}
void decomp(int node, int par) {
  kol[node] = djeca(node, par);
  int sad = centr(node, par, kol[node]);
  broji(sad, -1, 0, 0, 0);
  dfs(sad, -1, 0, 0, 0, 0);
  m.clear();
  gotov[sad] = 1;
  for (int i = 0; i < v[sad].size(); i++) {
    if (!gotov[v[sad][i].first]) decomp(v[sad][i].first, node);
  }
  return;
}
void solve() {
  cin >> n >> MOD;
  for (int i = 0; i < n - 1; i++) {
    cin >> a >> b >> c;
    v[a].push_back(make_pair(b, c));
    v[b].push_back(make_pair(a, c));
  }
  long long int k = MOD;
  long long int result = MOD;
  for (int p = 2; p * p <= k; ++p) {
    if (k % p == 0) {
      while (k % p == 0) k /= p;
      result -= result / p;
    }
  }
  if (k > 1) result -= result / k;
  FI = result;
  for (int i = 0; i <= n; i++) {
    inv1[i] = powmod(10, i);
  }
  for (int i = 0; i <= n; i++) {
    inv[i] = powmod(inv1[i], FI - 1);
  }
  decomp(0, -1);
  cout << sol << endl;
  return;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  solve();
  return 0;
}
