#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

int n;
LL k;
vector<vector<pair<int, int>>> graph;

vector<int> criteria;
int act_p;

constexpr int mod = int(1e9) + 7;

int add(int a, int b) {
	a += b;
	if(a >= mod)
		a -= mod;
	return a;
}

int mul(int a, int b) {
	return int(a * LL(b) % mod);
}

vector<int> potn;

struct Hash {
	int sum1 = 0, sum2 = 0;
	Hash(int, int);
	Hash(vector<int>&);
	Hash& addd(int);
	Hash &rm(int);
	Hash complementary();
};
Hash goal(0, 0);
Hash::Hash(int x, int y) : sum1(x), sum2(y) {}
Hash::Hash(vector<int> &vec) {
	REP(i, size(vec)) {
		sum1 = add(sum1, mul(potn[i], vec[i]));
		sum2 += vec[i];
	}
}

Hash& Hash::addd(int pi) {
	sum1 = add(sum1, potn[pi]);
	++sum2;
	return *this;
}

Hash& Hash::rm(int pi) {
	sum1 = add(sum1, mod - potn[pi]);
	--sum2;
	return *this;
}

Hash Hash::complementary() {
	return Hash(add(goal.sum1, mod - sum1), goal.sum2 - sum2);
}
//struct HashHash {
	//size_t operator()(const Hash &h) const {
		//return hash<int>()(h.sum);
	//}
//};
bool operator<(const Hash &l, const Hash &r) {
	if(l.sum1 == r.sum1)
		return l.sum2 < r.sum2;
	return l.sum1 < r.sum1;
}
bool operator==(const Hash &l, const Hash &r) {
	return l.sum1 == r.sum1 and l.sum2 == r.sum2;
}
ostream& operator<<(ostream &os, const Hash &h) {
	return os << h.sum1;
}

vector<bool> can_pass;
vector<int> subsize;

void sz_dfs(int v, int p = -1) {
	subsize[v] = 1;
	for(auto &x : graph[v])
		if(x.first != p and can_pass[x.first]) {
			sz_dfs(x.first, v);
			subsize[v] += subsize[x.first];
		}
}

int find_centroid(int v, int r, int p = -1) {
	for(auto &x : graph[v])
		if(x.first != p and can_pass[x.first] && 2 * subsize[x.first] >= subsize[r])
			return find_centroid(x.first, r, v);
	return v;
}

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
//typedef cc_hash_table<int, int, hash<int>> ht;
//unordered_map<Hash, vector<int>, HashHash> answers;
//cc_hash_table<Hash, vector<int>, HashHash> answers;
map<Hash, vector<int>> answers;
vector<int> path_cnt;
Hash act(0, 0);
vector<int> curr;

bool add_edge(int w, int delta) {
	if(w >= act_p) {
		if(w > act_p and delta == 1 and curr[w] + 1 > criteria[w])
			return false;
		curr[w] += delta;
	}
	if(w > act_p) { 
		if(delta == 1)
			act.addd(w);
		else
			act.rm(w);
	}
	return true;
}

void add_value(vector<int> &v, int i) {
	if(int(v.size()) <= i)
		v.resize(i + 1);
	++v[i];
}

void add_subtree(int v, int p = -1) {
	debug() << "adding subtree of " << v << " with hash " << act;
	add_value(answers[act], curr[act_p]);
	for(auto &x : graph[v]) {
		int u = x.first, w = x.second;
		if(u != p and can_pass[u]) {
			if(not add_edge(w, 1))
				continue;
			add_subtree(u, v);
			add_edge(w, -1);
		}
	}
}

int mx_cnt = 0;

void ask_subtree(int v, int p = -1) {
	debug() << "asking subtree of " << v;
	debug() << "trying to find hash " << act.complementary();
	auto it = answers.find(act.complementary());
	if(it != answers.end()) {
		debug() << "from vertex " << v << " adding splot " << make_pair(curr[act_p], it->second);
		REP(j, size(it->second)) {
			path_cnt[curr[act_p] + j] += it->second[j];
			mx_cnt = max(mx_cnt, curr[act_p] + j);
		}
	}

	for(auto &x : graph[v]) {
		int u = x.first, w = x.second;
		if(u != p and can_pass[u]) {
			if(not add_edge(w, 1))
				continue;
			ask_subtree(u, v);
			add_edge(w, -1);
		}
	}
}

void decomposition(int v = 0) {
	sz_dfs(v);
	v = find_centroid(v, v);
	answers.clear();
	answers[Hash(0, 0)] = {1};
	can_pass[v] = false;
	debug() << "starting from " << v;
	for(auto &x : graph[v]) {
		debug() << "considering child " << x;
		int u = x.first, w = x.second;
		if(can_pass[u]) {
			debug() << "visiting son " << u;
			if(not add_edge(w, 1))
				continue;
			ask_subtree(u, v);
			add_subtree(u, v);
			add_edge(w, -1);
		}
	}
	debug() << "after traversing: map = " << answers;

	for(auto &x : graph[v])
		if(can_pass[x.first])
			decomposition(x.first);
	can_pass[v] = true;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

#ifdef TIMER
	//n = 25000;
	n = 5000;
	k = 0;
#else
	cin >> n >> k;
#endif

	
	graph.resize(n);
	int mx_p = 0;
	vector<int> weight_cnt(n);
	REP(edge, n - 1) {
		int v, u, p;
#ifdef TIMER
		v = edge + 2;
		u = rd(1, edge + 1);
		p = rd(1, n);
#else
		cin >> v >> u >> p;
#endif
		--v, --u, --p;
		graph[v].emplace_back(u, p);
		graph[u].emplace_back(v, p);
		++weight_cnt[p];
		mx_p = max(mx_p, p);
	}
	potn.resize(n + 1, n);
	for(int i = 1; i <= n; ++i)
		potn[i] = mul(potn[i - 1], n);
	++mx_p;
	debug(n, k, mx_p);
	k = n * (n - 1) / 2 - k;
	debug(n, k);
	debug(graph);

	can_pass.resize(n, true);
	subsize.resize(n, 0);
	curr.resize(mx_p);

	// answers.max_load_factor(0.25);
	criteria.resize(mx_p);
	path_cnt.resize(n);
	for(act_p = mx_p - 1; act_p >= 0; --act_p) {
		if(weight_cnt[act_p] == 0)
			continue;
		debug() << '\n' << "starting for act_p = " << act_p;
		mx_cnt = 0;
		goal = Hash(criteria);
		debug(act_p, criteria, goal);
		decomposition();
		debug(can_pass);
		debug(path_cnt);

		for(int c = weight_cnt[act_p]; c >= 0; --c)
			if(k + 1 <= path_cnt[c] and path_cnt[c] > 0) {
				criteria[act_p] = c;
				break;
			}
			else
				k -= path_cnt[c];
		debug(criteria[act_p]);

		FOR(i, 0, weight_cnt[act_p])
			path_cnt[i] = 0;
	}
	debug(criteria);

	cout << Hash(criteria).sum1;
}