#include <bits/stdc++.h>
using namespace std;
bool isprime[100005];
vector<long long> primes;
vector<pair<int, int> > adj[100005];
int subsize[100005];
bool visited[100005];
int treesize;
vector<int> clrlist;
long long up[100005];
long long down[100005];
long long pre[100005], pre_inv[100005];
int h[100005];
int PHI;
long long mod;
int n;
int dppart[100005];
long long mult(long long a, long long b) { return (a * b) % mod; }
long long add(long long a, long long b) { return (a + b + mod) % mod; }
long long modpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
void sieve(int n) {
  memset(isprime, 1, sizeof isprime);
  isprime[1] = false;
  for (int i = 2; i <= n; i++) {
    if (isprime[i]) {
      primes.push_back(i);
      for (int j = 2 * i; j <= n; j += i) {
        isprime[j] = false;
      }
    }
  }
}
int phi(int n) {
  long long num = 1;
  long long num2 = n;
  for (long long i = 0; primes[i] * primes[i] <= n; i++) {
    if (n % primes[i] == 0) {
      num2 /= primes[i];
      num *= (primes[i] - 1);
    }
    while (n % primes[i] == 0) {
      n /= primes[i];
    }
  }
  if (n > 1) {
    num2 /= n;
    num *= (n - 1);
  }
  n = 1;
  num *= num2;
  return num;
}
long long inv(long long a) { return modpow(a, PHI - 1); }
void dfs(int cur, int prev) {
  if (prev == -1) clrlist.clear();
  subsize[cur] = 1;
  clrlist.push_back(cur);
  for (int i = 0; i < adj[cur].size(); i++) {
    int node = adj[cur][i].first;
    if (visited[node]) continue;
    if (node == prev) continue;
    dfs(node, cur);
    subsize[cur] += subsize[node];
  }
  if (prev == -1) treesize = subsize[cur];
}
int centroid(int cur, int prev) {
  for (int i = 0; i < adj[cur].size(); i++) {
    int node = adj[cur][i].first;
    if (visited[node]) continue;
    if (node == prev) continue;
    if (subsize[node] > treesize / 2) return centroid(node, cur);
  }
  return cur;
}
int parts = 0;
void partition_nodes(int cur, int prev, int cent) {
  if (prev == cent) {
    dppart[cur] = parts;
    parts++;
  } else if (prev != -1) {
    dppart[cur] = dppart[prev];
  }
  for (int i = 0; i < adj[cur].size(); i++) {
    int node = adj[cur][i].first;
    int w = adj[cur][i].second;
    if (node == prev || visited[node]) continue;
    down[node] = add(mult(down[cur], 10), w);
    up[node] = add(up[cur], mult(pre[h[cur]], w));
    h[node] = h[cur] + 1;
    partition_nodes(node, cur, cent);
  }
}
long long solve(int cent) {
  for (int i = 0; i < clrlist.size(); i++) {
    up[clrlist[i]] = 0;
    down[clrlist[i]] = 0;
    h[clrlist[i]] = 0;
  }
  parts = 0;
  partition_nodes(cent, -1, cent);
  parts--;
  dppart[cent] = -1;
  map<long long, long long> tot;
  vector<map<long long, long long> > vec;
  vec.resize(parts + 1);
  tot[0]++;
  for (int i = 0; i < clrlist.size(); i++) {
    int node = clrlist[i];
    if (node == cent) continue;
    tot[up[node]]++;
    vec[dppart[node]][up[node]]++;
  }
  long long ans = 0;
  for (int i = 0; i < clrlist.size(); i++) {
    int node = clrlist[i];
    int ht = h[node];
    int pt = dppart[node];
    if (node == cent) {
      ans += (tot[0] - 1);
    } else {
      long long val = ((-down[node]) % mod + mod) % mod;
      val = mult(val, pre_inv[ht]);
      ans += (tot[val] - vec[pt][val]);
    }
  }
  return ans;
}
long long compsolve(int cur) {
  dfs(cur, -1);
  int cent = centroid(cur, -1);
  long long ans = solve(cent);
  visited[cent] = true;
  for (int i = 0; i < adj[cent].size(); i++) {
    int node = adj[cent][i].first;
    if (!visited[node]) ans += compsolve(node);
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> mod;
  if (mod == 1) {
    cout << n * 1ll * (n - 1) << "\n";
    return 0;
  }
  sieve(100000);
  PHI = phi(mod);
  pre[0] = 1;
  for (int i = 1; i <= 100000; i++) pre[i] = (10 * pre[i - 1]) % mod;
  for (int i = 0; i <= 100000; i++) pre_inv[i] = modpow(pre[i], PHI - 1);
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
  }
  cout << compsolve(0) << "\n";
  return 0;
}
