#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int> > > g;
vector<int> d, s, act, to, dep;
long long ans = 0;
int k, c;
vector<bool> w;
void dfs(int n, int p)
{
    s[n] = 1;
    for(auto x : g[n])
    {
        int y = x.first;
        if(y != p && !w[y])
        {
            dfs(y, n);
            s[n] += s[y];
        }
    }
}
int fc(int n, int p)
{
    for(auto x : g[n])
    {
        int y = x.first;
        if(!w[y] && y != p)
        {
            if(s[y] > c / 2) return fc(y, n);
        }
    }
    return n;
}
void add(int n, int p)
{
    act.push_back(n);
    to.push_back(n);
    ans += dep[(k - d[n]) % k];
    for(auto x : g[n])
    {
        int y = x.first;
        if(!w[y] && y != p)
        {
            d[y] = (d[n] + x.second) % k;
            add(y, n);
        }
    }
}
void solve(int n)
{
    dfs(n, 0);
    c = s[n];
    int u = fc(n, 0);
    w[u] = 1;
    dep[0]++;
    to.clear();
    for(auto x : g[u])
    {
        int y = x.first;
        if(!w[y])
        {
            act.clear();
            d[y] = x.second % k;
            add(y, u);
            for(auto x : act)
            {
                dep[d[x]]++;
            }
        }
    }
    for(auto x : to) dep[d[x]]--;
    dep[0]--;
    for(auto x : g[u])
    {
        int y = x.first;
        if(!w[y]) solve(y);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n >> k;
    g.resize(n + 1);
    d.resize(n + 1);
    w.resize(n + 1);
    s.resize(n + 1);
    dep.resize(k);
    for(int i = 0; i < n - 1; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
    solve(1);
    cout << ans;
}