#include <bits/stdc++.h>
using namespace std;

vector<vector<array<int, 2>>> g;
int n, k, ans = 0;
vector<vector<int>> a;

void dfs(int v, int p){
    a[v][0] = 1;
    for(auto [x, w] : g[v]){
        if(x == p) continue;
        dfs(x, v);
        for(int i = 0; i < k; i++){
            ans += a[x][i] * a[v][(2 * k - i - w) % k];
        }
        for(int i = 0; i < k; i++){
            a[v][i] += a[x][(i + w) % k];
        }
    }
}

int main() {
    cin >> n >> k;
    g.resize(n + 1);
    a.resize(n + 1, vector<int>(k));
    for(int i = 0; i < n - 1; i++){
        int b, c, d;
        cin >> b >> c >> d;
        g[b].push_back({c, d});
        g[c].push_back({b, d});
    }
    dfs(1, 0);
    cout << ans;
}