#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <queue>
#include <algorithm>

using namespace std;
using ll = long long int;
int k;
vector<pair<int,int>> g[50010];
ll dp[50010][1010] = { 0 };
ll sol = 0;        //lehet overflow

void dfs(int node, int prev = -1) {
    dp[node][0] = 1;
    for (auto i : g[node]) {
        if (i.first != prev) {
            dfs(i.first, node);
            ll mock[1010] = { 0 };
            for (int j = 0; j < k; ++j) {
                int kellmeg = (k - ((j + i.second) % k)) % k;
                //cerr << ((j + i.second) % k) << " " << kellmeg << endl;
               // cerr << node << endl;
               // cerr << j << " " << i.second << " " << kellmeg << " " << dp[node][kellmeg] * dp[i.first][j] << endl;
                sol += dp[node][kellmeg] * dp[i.first][j];
                mock[(j + i.second) % k] += dp[i.first][j];
            }
            for (int j = 0; j < k; ++j) {
                dp[node][j] += mock[j];
            }
        }
    }
}

int main()
{
    int n;
    cin >> n >> k;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, t;
        cin >> a >> b >> t;
        g[a].emplace_back(b, t);
        g[b].emplace_back(a, t);
    }
    //cerr << endl << endl;
    dfs(1);
    cout << sol << endl;
    /*for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < k; ++j) {
            cerr << dp[i][j] << " ";
        }
        cerr << endl;
    }*/
    return 0;
}