#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

struct edge {
    int to, w;
    edge(int TO, int W) {
        to = TO;
        w = W;
    }
};

int n, k, c, sz;
ll wsum, ans = 0;
vector <bool> volt(5e4 + 1, false);
vector <vector <edge>> g(5e4 + 1);
vector <int> cnt(1e3, 0);

int get_c(int x) {
    if (volt[x]) return 0;
    volt[x] = true;
    int cur, sum = 1;
    bool cen = true;
    for (edge e : g[x]) {
        cur = get_c(e.to);
        sum += cur;
        if (cur > sz / 2) cen = false;
    }
    if (sz - sum > sz / 2) cen = false;
    if (cen) c = x;
    volt[x] = false;
    return sum;
}

void dfs1(int x) {
    if (volt[x]) return;
    volt[x] = true;
    ans += cnt[(k - wsum % k) % k];
    for (edge e : g[x]) {
        wsum += e.w;
        dfs1(e.to);
        wsum -= e.w;
    }
    volt[x] = false;
}

void dfs2(int x) {
    if (volt[x]) return;
    volt[x] = true;
    cnt[wsum % k]++;
    for (edge e : g[x]) {
        wsum += e.w;
        dfs2(e.to);
        wsum -= e.w;
    }
    volt[x] = false;
}

void solve(int x) {
    if (volt[x]) return;
    sz = get_c(x);
    get_c(x);
    volt[c] = true;
    fill(cnt.begin(), cnt.end(), 0);
    cnt[0] = 1;
    for (edge e : g[c]) {
        wsum = e.w;
        dfs1(e.to);
        dfs2(e.to);
    }
    int C = c;
    for (edge e : g[C]) solve(e.to);
}

int main()
{
    cin >> n >> k;
    int a, b, W;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b >> W;
        g[a].push_back(edge(b, W));
        g[b].push_back(edge(a, W));
    }
    solve(1);
    cout << ans;
}