1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long power(long long b, int e){
	if(e==0)
		return 1;
	long long x=power(b, e/2);
	x=x*x;
	return (e%2)?(x*b):x;
}

struct Edge{
	int t;
	long long w;
};

long long PathLen(int v, int target, const vector<vector<Edge>> &G, int p=-1){
	if(v==target)
		return 0;
	for(Edge e : G[v])
		if(e.t!=p){
			long long retval = PathLen(e.t, target, G, v);
			if(retval>=0)
				return retval+e.w;
		}
	return -1;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n,k;
	cin >> n >> k;

	vector<vector<Edge>>Graf(n+1);
	for(int i=1;i<n;i++){
		int a,b,p;
		cin >> a >> b >> p;
		long long P = power(n,p);
		Graf[a].push_back({b,P});
		Graf[b].push_back({a,P});
	}
	
	vector<long long>Paths;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			Paths.push_back(PathLen(i, j, Graf));
	sort(Paths.begin(), Paths.end());
	
	cout << Paths[k-1]%1000000007 << "\n";
	
	return 0;
}