#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long maxn = 1e5 + 7;
const long long maxe = 1e6 + 7;
const long long INF = 1e9 + 7;
const double PI = acos(-1);
int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};
inline void Max(int &a, int b) {
  if (b > a) a = b;
}
inline void Min(int &a, int b) {
  if (a == -1 || b < a) a = b;
}
int n;
long long M;
vector<pair<int, int> > G[maxn];
bool cen[maxn];
int si[maxn];
long long p10[maxn];
long long ni[maxn];
long long ans;
void calsize(int v, int p) {
  si[v] = 1;
  for (int i = 0; i < G[v].size(); i++) {
    int u = G[v][i].first;
    if (u == p || cen[u]) continue;
    calsize(u, v);
    si[v] += si[u];
  }
}
pair<int, int> findcen(int v, int p, int t) {
  int s = 1, m = 0;
  pair<int, int> res = make_pair(INF, -1);
  for (int i = 0; i < G[v].size(); i++) {
    int u = G[v][i].first;
    if (u == p || cen[u]) continue;
    res = min(res, findcen(u, v, t));
    s += si[u];
    m = max(si[u], m);
  }
  m = max(m, t - s);
  res = min(res, make_pair(m, v));
  return res;
}
void getpath(int v, int p, int w1, int w2, int l, vector<int> &ts1,
             vector<pair<int, int> > &ts2) {
  ts1.push_back(w1);
  ts2.push_back(make_pair(w2, l));
  for (int i = 0; i < G[v].size(); i++) {
    int u = G[v][i].first;
    int w = G[v][i].second;
    if (u == p || cen[u]) continue;
    long long nw1 = (w1 + 1ll * w * p10[l]) % M;
    long long nw2 = (1ll * w2 * 10 + w) % M;
    getpath(u, v, (int)nw1, (int)nw2, l + 1, ts1, ts2);
  }
}
long long run(vector<int> &ts1, vector<pair<int, int> > &ts2) {
  sort((ts1).begin(), (ts1).end());
  long long res = 0;
  for (int i = 0; i < ts2.size(); i++) {
    long long num = ts2[i].first;
    int l = ts2[i].second;
    long long ned = 1ll * (M - num) * ni[l] % M;
    res += upper_bound((ts1).begin(), (ts1).end(), (int)ned) -
           lower_bound((ts1).begin(), (ts1).end(), (int)ned);
  }
  return res;
}
void solve(int v) {
  calsize(v, -1);
  int s = findcen(v, -1, si[v]).second;
  cen[s] = true;
  for (int i = 0; i < G[s].size(); i++) {
    int u = G[s][i].first;
    if (!cen[u]) solve(u);
  }
  vector<int> ds1;
  vector<pair<int, int> > ds2;
  ds1.push_back(0);
  ds2.push_back(make_pair(0, 0));
  for (int i = 0; i < G[s].size(); i++) {
    int u = G[s][i].first;
    int w = G[s][i].second;
    if (cen[u]) continue;
    vector<int> ts1;
    vector<pair<int, int> > ts2;
    getpath(u, s, w % M, w % M, 1, ts1, ts2);
    ans -= run(ts1, ts2);
    ds1.insert(ds1.end(), (ts1).begin(), (ts1).end());
    ds2.insert(ds2.end(), (ts2).begin(), (ts2).end());
  }
  cen[s] = false;
  ans += run(ds1, ds2);
}
long long qpow(long long x, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) res = res * x % M;
    x = x * x % M;
    n >>= 1;
  }
  return res;
}
long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long d = a;
  if (b == 0) {
    x = 1;
    y = 0;
  } else {
    d = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
  return d;
}
long long inver(long long a, long long m) {
  long long x, y;
  extgcd(a, m, x, y);
  return (x % m + m) % m;
}
void init() {
  p10[0] = 1;
  ni[0] = 1;
  for (int i = 1; i < maxn; i++) {
    p10[i] = p10[i - 1] * 10 % M;
    ni[i] = inver(p10[i], M);
  }
}
int main() {
  cin >> n >> M;
  if (M == 1) {
    cout << 1ll * (n - 1) * (n) << endl;
    return 0;
  }
  init();
  for (int i = 0; i < n - 1; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u++, v++;
    G[u].push_back(make_pair(v, w));
    G[v].push_back(make_pair(u, w));
  }
  solve(1);
  ans -= n;
  cout << ans << endl;
  ;
  return 0;
}
