#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int n,k;

vector<vector<pair<int,int>>> g;
vector<int> sz;
vector<bool> iscent;
int res;
void cent(int v, int tsize, int p=-1){
    sz[v]=1;
    for (auto [to, c] : g[v]) {
        if (to==p || iscent[to]) continue;
        cent(to, tsize, v);
        sz[v]+=sz[to];
    }
    if (!res && 2*sz[v]>=tsize) {
        res=v;
    }
}

vector<int> rem, ans;
ll valasz;

void dfs(int v, int d, int p=-1){
    if (iscent[v]) return;
    rem.push_back(d%k);
    for (auto [to,c] : g[v]){
        if (p==to ) continue;

        dfs(to, d+c, v);
    }
}

void solve(int v, int tsize){
    if (iscent[v]) return;
    res=0;
    cent(v,tsize);
    iscent[res]=true;
    // res-re szamolas
    vector<int> change = {0};
    ans[0]=1;  
    for (auto [to,c] : g[res]){
        rem.clear();
        dfs(to, c);
        for (int i : rem){
            change.push_back(i);
            valasz+=ans[(k-i)%k];
        }
        for (int i : rem) ans[i]++;
    }
    for (int i : change) ans[i]=0;

    vector<pair<int,int>> nxt;
    for (auto [to,c] : g[res]) {
        int val=sz[to];
        if (2*val>tsize) {
            val=tsize-sz[res];
        }
        nxt.push_back({to, val});
    }
    for (auto [i,j] : nxt) solve(i,j);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n>>k;
    g.resize(n+1);
    sz.resize(n+1);
    iscent.resize(n+1,false);
    ans.resize(k,0);
    for (int i=0;i<n-1;i++){
        int a,b,t;
        cin>>a>>b>>t;
        g[a].push_back({b,t});
        g[b].push_back({a,t});
    }
    solve(1, n);
    cout<<valasz<<"\n";
}