#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > AdjList[100010];
int subSize[100010];
int used[100010];
long long up[100010];
long long down[100010];
int nvl[100010];
int n;
long long MOD, INV;
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long X, Y;
  long long g = ext_gcd(b, a % b, X, Y);
  x = Y;
  y = X - Y * (a / b);
  return g;
}
bool find_solution(long long a, long long b, long long c, long long &x,
                   long long &y, long long &g) {
  g = ext_gcd(abs(a), abs(b), x, y);
  if (c % g != 0) return false;
  long long k = c / g;
  x *= k;
  y *= k;
  if (a < 0) x = -x;
  if (b < 0) y = -y;
  return true;
}
long long fast_pow(long long base, int exp) {
  long long res = 1;
  for (int i = 0; i < 31; i++) {
    if ((exp & (1 << i)) != 0) {
      res *= base;
      res = res % MOD;
    }
    base *= base;
    base = base % MOD;
  }
  return res;
}
void calcSubSize(int x, int p = -1) {
  subSize[x] = 1;
  for (pair<int, int> y : AdjList[x]) {
    if (y.first == p || used[y.first]) continue;
    calcSubSize(y.first, x);
    subSize[x] += subSize[y.first];
  }
}
int findCentroid(int x, int treeSize) {
  for (pair<int, int> y : AdjList[x]) {
    if (subSize[y.first] > subSize[x] || used[y.first]) continue;
    if (2 * subSize[y.first] > treeSize) return findCentroid(y.first, treeSize);
  }
  return x;
}
void getPaths(map<long long, int> &UP, map<pair<int, long long>, int> &DOWN,
              int x, long long pot10, int p) {
  if (UP.find(up[x]) == UP.end()) UP[up[x]] = 0;
  UP[up[x]]++;
  if (DOWN.find(make_pair(nvl[x], down[x])) == DOWN.end())
    DOWN[make_pair(nvl[x], down[x])] = 0;
  DOWN[make_pair(nvl[x], down[x])]++;
  for (pair<int, int> e : AdjList[x]) {
    int y = e.first;
    int dig = e.second;
    if (y == p || used[y]) continue;
    nvl[y] = nvl[x] + 1;
    down[y] = ((down[x] * 10) % MOD + dig) % MOD;
    up[y] = (up[x] + (dig * pot10) % MOD) % MOD;
    getPaths(UP, DOWN, y, (pot10 * 10) % MOD, x);
  }
}
long long centroidDecomp(int x) {
  calcSubSize(x);
  int centroid = findCentroid(x, subSize[x]);
  long long ans = 0;
  map<long long, int> totalUp;
  vector<map<pair<int, long long>, int> > DOWN;
  vector<map<long long, int> > UP;
  for (pair<int, int> e : AdjList[centroid]) {
    if (used[e.first]) continue;
    up[e.first] = e.second % MOD;
    down[e.first] = e.second % MOD;
    nvl[e.first] = 1;
    UP.push_back(map<long long, int>());
    DOWN.push_back(map<pair<int, long long>, int>());
    getPaths(UP.back(), DOWN.back(), e.first, 10 % MOD, centroid);
    for (pair<long long, int> pp : UP.back()) {
      if (pp.first == 0) ans += pp.second;
      if (totalUp.find(pp.first) == totalUp.end()) totalUp[pp.first] = 0;
      totalUp[pp.first] += pp.second;
    }
  }
  for (int i = 0; i < UP.size(); i++) {
    for (pair<pair<int, long long>, int> pp : DOWN[i]) {
      long long dDown = pp.first.second;
      long long h = pp.first.first;
      if (dDown == 0) ans += pp.second;
      long long dUp = (MOD - (dDown * fast_pow(INV, h)) % MOD) % MOD;
      if (totalUp.find(dUp) != totalUp.end())
        ans += (totalUp[dUp] - UP[i][dUp]) * pp.second;
    }
  }
  used[centroid] = true;
  for (pair<int, int> e : AdjList[centroid]) {
    if (!used[e.first]) ans += centroidDecomp(e.first);
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> MOD;
  for (int i = 0; i < n - 1; i++) {
    int a, b, d;
    cin >> a >> b >> d;
    AdjList[a].push_back(make_pair(b, d));
    AdjList[b].push_back(make_pair(a, d));
  }
  long long y, g;
  find_solution(10, MOD, 1, INV, y, g);
  INV = (INV + MOD) % MOD;
  cout << centroidDecomp(0) << "\n";
  return 0;
}
