#include <bits/stdc++.h>
using namespace std;
int n, mod;
int add(int x, int y) {
  x += y;
  while (x >= mod) x -= mod;
  while (x < 0) x += mod;
  return x;
}
int mul(int x, int y) { return (x * 1LL * y) % mod; }
int gcdExtended(int a, int b, int *x, int *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  int x1, y1, gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
int getInv(int a, int m = mod) {
  int x, y;
  int g = gcdExtended(a, m, &x, &y);
  assert(g == 1);
  int res = (x % m + m) % m;
  return res;
}
class Map {
 public:
  map<int, int> M;
  int addOff, mulOff;
  Map() {
    addOff = 0;
    mulOff = 1;
  }
  void convertToBaseValue(int &x) { x = add(mul(x, getInv(mulOff)), -addOff); }
  void convertToRealValue(int &x) { x = mul(add(x, addOff), mulOff); }
  virtual void move(int c) = 0;
  int getOcc(int x) {
    convertToBaseValue(x);
    if (M.find(x) == M.end()) return 0;
    return M[x];
  }
  void addItem(int x, int occs) {
    convertToBaseValue(x);
    M[x] += occs;
  }
};
class SuffixMap : public Map {
 public:
  void move(int c) {
    int mulOff2 = mul(mulOff, getInv(10));
    int addOff2 =
        mul(mul(add(c, mul(addOff, mulOff)), getInv(10)), getInv(mulOff2));
    addOff = addOff2;
    mulOff = mulOff2;
  }
};
class PrefixMap : public Map {
 public:
  void move(int c) {
    int mulOff2 = mul(mulOff, 10);
    int addOff2 = mul(add(mul(mul(addOff, mulOff), 10), c), getInv(mulOff2));
    addOff = addOff2;
    mulOff = mulOff2;
  }
};
vector<pair<int, int> > g[100005];
int cnt[100005];
int maxChild[100005];
long long ans = 0;
void setTree(int node, int parent) {
  cnt[node] = 1;
  maxChild[node] = -1;
  for (int i = 0; i < int(g[node].size()); i++) {
    int child = g[node][i].first;
    if (child == parent) continue;
    setTree(child, node);
    cnt[node] += cnt[child];
    if (maxChild[node] == -1 || cnt[child] > cnt[maxChild[node]])
      maxChild[node] = child;
  }
}
void solve(int node, int parent, vector<Map *> v) {
  for (int i = 0; i < int(g[node].size()); i++) {
    int child = g[node][i].first;
    if (child != maxChild[node]) continue;
    solve(child, node, v);
    for (int j = 0; j < int(v.size()); j++)
      v[j]->addItem(0, 1), v[j]->move(g[node][i].second),
          ans += v[j]->getOcc(0);
  }
  for (int i = 0; i < int(g[node].size()); i++) {
    int child = g[node][i].first;
    if (child == parent || child == maxChild[node]) continue;
    vector<Map *> vv;
    vv.push_back(new PrefixMap());
    vv.push_back(new SuffixMap());
    solve(child, node, vv);
    for (int j = 0; j < int(vv.size()); j++)
      vv[j]->addItem(0, 1), vv[j]->move(g[node][i].second),
          ans += vv[j]->getOcc(0);
    for (int j = 0; j < int(vv.size()); j++) {
      for (map<int, int>::iterator it = vv[j]->M.begin(); it != vv[j]->M.end();
           it++) {
        int val = it->first;
        vv[j]->convertToRealValue(val);
        val = add(-val, mod);
        ans += v[1 - j]->getOcc(val) * 1LL * it->second;
      }
    }
    for (int j = 0; j < int(vv.size()); j++) {
      for (map<int, int>::iterator it = vv[j]->M.begin(); it != vv[j]->M.end();
           it++) {
        int val = it->first;
        vv[j]->convertToRealValue(val);
        v[j]->addItem(val, it->second);
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  scanf("%d%d", &n, &mod);
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    g[u].push_back(make_pair(v, w));
    g[v].push_back(make_pair(u, w));
  }
  int root = rand() % n;
  setTree(root, -1);
  vector<Map *> v;
  v.push_back(new PrefixMap());
  v.push_back(new SuffixMap());
  solve(root, -1, v);
  printf("%lld\n", ans);
  return 0;
}
