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

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,K;
	cin>>N>>K;
	vector<vector<pair<int,int>>>g(N+1);
	for(int i=0;i<N-1;i++){
		int a,b,d;
		cin>>a>>b>>d;
		g[a].emplace_back(b,d);
		g[b].emplace_back(a,d);
	}
	int ans=0;
	auto dfs=[&](auto self,int i,int p,int x)->map<int,int>{
		map<int,int>s;
		for(auto[j,d]:g[i]){
			if(j==p){
				continue;
			}
			auto z=self(self,j,i,x+d);
			ans+=z[x%K];
			if(z.size()>s.size()){
				swap(s,z);
			}
			for(auto[y,c]:z){
				ans+=s[((x*2-y)%K+K)%K]*c;
			}
			for(auto[y,c]:z){
				s[y]+=c;
			}
		}
		s[x%K]++;
		return s;
	};
	dfs(dfs,1,0,0);
	cout<<ans<<'\n';
	return 0;
}