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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// Karol Kosinski 2019
#include <cstdio>
#include <algorithm>
#include <vector>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FOD(i,b,a) for(int i=(b-1);i>=(a);--i)
//#define DEBUG(x...) printf(x)
#define DEBUG(x...)
using namespace std;

typedef unsigned long long LL;
const int NX = 10009;
const LL MOD = 1'000'000'007;

struct Edge
{
    int aim; LL val;
};

LL E[NX * NX];
int e_top = 0;
vector<Edge> G[NX];
bool Was[NX];
LL D[NX];

LL pow(int n, int p)
{
    LL res = 1;
    FOR(i,0,p) res *= n;
    return res;
}

void dfs(int ind)
{
    Was[ind] = true;
    const auto &V = G[ind];
    for(const auto &ed : V)
    {
        if (Was[ed.aim]) continue;
        Was[ed.aim] = true;
        D[ed.aim] = D[ind] + ed.val;
        dfs(ed.aim);
    }
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    FOR(i,1,n)
    {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        LL pp = pow(n, p);
        G[a].push_back((Edge){b, pp});
        G[b].push_back((Edge){a, pp});
    }
    FOD(i,n+1,1)
    {
        dfs(i);
        FOD(j,n+1,1)
        {
            if (i == j) continue;
            E[e_top++] = D[j];
            DEBUG("%d(%llu) ", j, D[j]);
        }
        FOD(j,n+1,1)
        {
            Was[j] = false;
            D[j] = 0;
        }
        DEBUG("\n");
    }
    nth_element(E, E + 2*k - 1, E + e_top);
    printf("%llu\n", E[2*k - 1] % MOD);
    return 0;
}