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

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

void dfs(long long v, long long p){
    a[v][0] = 1;
    for(auto [x, w] : g[v]){
        if(x == p) continue;
        dfs(x, v);
        for(long long i = 0; i < k; i++){
            ans += a[x][i] * a[v][(4 * k - i - w) % k];
        }
        for(long long 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<long long>(k, 0));
    for(long long i = 0; i < n - 1; i++){
        long long 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";
    }*/
}