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

vector<vector<array<int, 2>>> g;
long long 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 += (long long)a[x][i] * (long long)a[v][(4 * k - i - w) % k];
        }
        for(int i = 0; i < k; i++){
            a[v][(i + w) % k] += a[x][i];
        }
    }
}

int main() {
    cin >> n >> k;
    g.resize(n + 1);
    a.resize(n + 1, vector<int>(k, 0));
    for(int i = 0; i < n - 1; i++){
        int b, c, d;
        cin >> b >> c >> d;
        g[b].push_back({c, d % k});
        g[c].push_back({b, d % k});
    }
    dfs(1, 0);
    cout << ans << "\n";
    /*for(auto x : a){
        for(auto y : x) cout << y << " ";
        cout << "\n";
    }*/

}