#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define VI vector<int>
#define VPII vector<PII>
#define LL long long
#define LD long double
#define f first
#define s second
#define MP make_pair
#define PB push_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
#define SIZ(c) (int)(c).size()
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, b, e) for(int i = (b); i <= (int)(e); ++i)
#define FORD(i, b, e) for(int i = (b); i >= (int)(e); --i)
#define ULL unsigned LL
#define sim template<class n
sim, class s> ostream & operator << (ostream &p, pair<n, s> x)
{return p << "<" << x.f << ", " << x.s << ">";}
sim> auto operator << (ostream &p, n y) ->
typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type 
{int o = 0; p << "{"; for(auto c: y) {if(o++) p << ", "; p << c;} return p << "}";}
void dor() {cerr << endl;}
sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);}
sim, class s> void mini(n &p, s y) {if(p>y) p = y;}
sim, class s> void maxi(n &p, s y) {if(p<y) p = y;}
#ifdef DEB
#define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__)
#else
#define debug(...)
#endif 

#define I(x) #x " =", (x), " "
#define A(a, i) #a "[" #i " =", i, "] =", a[i], " "

// ******************************************************************************

int mod = 1e9+7;
const int MXN = 25002;
VPII V[MXN];

PII par[MXN];
short int depth[MXN];
int ID = 1;

int pos[MXN*2];
int where_pos[MXN*2];
short int segs[MXN*2][18];
short int nr[MXN*2];
int n;
bitset<MXN> B[MXN]; // 75 MB
bitset<MXN> B2[MXN]; // 75 MB
int byl_cost[MXN];

short int* ile[MXN]; // [i][j] ile jest krawędzi o koszcie j od roota
unsigned LL* h[MXN];

unsigned LL coeff[MXN];
int real_val[MXN];
int p;
int pots[MXN];


int ii = 0;
void dfs0(int x, int my_id, int pp)
  {
  pos[++ii] = my_id;
  where_pos[my_id] = ii;

  for(auto i : V[x])
    {
    if(i.f == pp)continue;
    par[++ID] = MP(my_id, i.s);
    dfs0(i.f, ID, x);
    pos[++ii] = my_id;
    }
  }
void lca_pre()
  {
  FOR(i, 1, ii)segs[i][0] = pos[i];
  FOR(j, 1, 17)
    FOR(i, 1, ii)
      {
      if((i + (1<<j)) > ii)continue;
      segs[i][j] = min(segs[i][j-1], segs[i + (1<<(j-1))][j-1]);
      }

  FORD(j, 17, 1)
    {
    FOR(i, (1<<(j)), min(1<<(j+1), MXN*2-1))
      {
      nr[i] = j;
      }
    }
  }

int lca3(int a, int b)
  {
  int poc = where_pos[a];
  int kon = where_pos[b];
  if(poc > kon)swap(poc, kon);
  int p = nr[kon - poc+1];

  return min(segs[poc][p], segs[kon-(1<<p)+1][p]);
  }


LL R(LL a, LL b){return (rand() * 1000000000LL + rand())%(b-a+1)+a;}

int wynik(int a, int b)
  {
  int l1 = lca3(a, b);

  LL res = 0;
  FOR(i, 1, p)
    {
    short int v1 = ile[a][i] + ile[b][i] - ile[l1][i]*2;

    res += (LL)pots[real_val[i]] * v1 % mod;
    res %= mod;
    }
  return res;
  }
int POTT = 0;
  
int cmp(int a, int b, int x, int y) // zwraca -1 jeśli cost(a, b) < cost(x, y)
  {
  int l1 = lca3(a, b);
  int l2 = lca3(x, y);
//  debug(a, b, x, y, l1, l2);

  if(h[a][1] + h[b][1] - h[l1][1] * 2 == h[x][1] + h[y][1] - h[l2][1]*2)return 0;

  int jestem = p+1;
  FORD(iter, POTT, 0)
    {
    int i = jestem - (1<<iter);
    if(i < 1)continue;

    if(h[a][i] + h[b][i] - h[l1][i]*2 == h[x][i] + h[y][i] - h[l2][i]*2)
      {
      jestem -= (1<<iter);
      }
    }
  int i = jestem-1;
  short int v1 = ile[a][i] + ile[b][i] - ile[l1][i]*2;
  short int v2 = ile[x][i] + ile[y][i] - ile[l2][i]*2;
  if(v1 < v2)return -1;
  else return 1;
  }

int dep = 0;
void go(int k)
  {      
//  debug(k); FOR(i, 1, n)FOR(j, 1, i-1)if(B[i][j])debug(i, j, I(wynik(i, j)));

  dep++;
  debug(I(dep));

  int cnt_ile = 0;
  FOR(i, 1, n)cnt_ile += B[i].count();


  int ktory = R(1, cnt_ile); // TODO: mediana z kilku losowych
  PII mam;
  FOR(i, 1, n)
    {
    int cnt = B[i].count();
    if(cnt >= ktory)
      {
      FOR(j, 1, i-1)
        {
        if(B[i][j])ktory--;
        if(ktory == 0)
          {
          mam = MP(i, j);
          break;
          }
        }
      }
    else
      {
      ktory -= cnt;
      }
    if(mam.f)break;
    }
//  assert(mam.f);

  VPII VV;
  REP(i, 1000)
    {
    int a = R(1, n);
    int b = R(1, n);
    if(a <= b)continue;
    if(B[a][b])VV.PB(MP(a, b));
    if(VV.size() > 100)break;
    }
  VV.PB(mam);

  sort(ALL(VV), [&](PII a, PII b){return cmp(a.f, a.s, b.f, b.s) == -1;});
  mam = VV[VV.size()/2];
  debug(I(VV.size()));



  debug(mam);  
  
  int mniejsze = 0;
  int rowne = 0;
  int wieksze = 0;
  FOR(i, 1, n)
    FOR(j, 1, i-1)
      {
      if(B[i][j])
        {
        int r = cmp(i, j, mam.f, mam.s);
        if(r == 0){B[i][j] = 0; rowne++;}

        if(r > 0){B2[i][j] = 1; wieksze++;} // wieksze
        if(r < 0){B2[i][j] = 0, mniejsze++;}
        }
      }
//  debug(cmp(mam.f, mam.s, mam.f, mam.s));
//  debug(I(mam), wynik(mam.f, mam.s));
  debug(mniejsze, rowne, wieksze, k, mniejsze + rowne + wieksze, cnt_ile);
//  assert(mniejsze + rowne + wieksze == cnt_ile);

  if(k <= mniejsze)
    {
    FOR(i, 1, n)
      B[i] &= B2[i].flip();

    go(k);
    return;
    }
  k -= mniejsze;
  if(k <= rowne)
    {
    cout << wynik(mam.f, mam.s) << endl;
    exit(0);
    }
  k -= rowne;
  FOR(i, 1, n)
    B[i] &= B2[i];

  go(k);
  }


int ile_p(int a, int b, int p)
  {
  int l1 = lca3(a, b);
  return ile[a][p] + ile[b][p] - ile[l1][p]*2;
  }

void go_small_p(int k, int ppp)
  {      
  debug(k, ppp, p);
//  debug(k); FOR(i, 1, n)FOR(j, 1, i-1)if(B[i][j])debug(i, j, I(wynik(i, j)));

  if(ppp == 0)
    {
    FOR(i, 1, n) FOR(j, 1, i-1) if(B[i][j]) 
      {
      cout << wynik(i, j) << endl;
      exit(0);
      }
//    assert(false);
    }

  VI pom(n+1);
  
  int mniejsze = 0;
  int rowne = 0;
  int wieksze = 0;
  FOR(i, 1, n)
    FOR(j, 1, i-1)
      {
      if(B[i][j])
        {
        pom[ile_p(i, j, ppp)]++;
        }
      }

  FOR(ILE, 0, n)
    {
    if(pom[ILE] >= k)
      {
      FOR(i, 1, n) FOR(j, 1, i-1) if(B[i][j])
        {
        if(ile_p(i, j, ppp) != ILE)B[i][j] = 0;
        }
      go_small_p(k, ppp-1);
      return;
      }
    else
      k -= pom[ILE];
    }
//  assert(false);
  }

int main()
  {
  int k;
  scanf("%d%d", &n, &k);
  pots[0] = 1; FOR(i, 1, n)pots[i] = (LL)pots[i-1] * n % mod;
  int rozne_p = 0;

  FOR(i, 1, n-1)
    {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    V[a].PB(MP(b, c));
    V[b].PB(MP(a, c));
    if(byl_cost[c] == 0)rozne_p++;
    byl_cost[c] = 1;
    }
  
  int root = rand() % n + 1;
  dfs0(root, 1, 0);
  lca_pre();

  FOR(i, 2, n)depth[i] = depth[par[i].f] + 1;

  p = 1;
  FOR(i, 1, n)if(byl_cost[i]){byl_cost[i] = p++;real_val[p-1] = i;} p--;
  debug(I(p));
  while((1 << (POTT+1)) <= p)POTT++;

  FOR(i, 0, n)
    {
    h[i] = new ULL[p+2];
    memset(h[i], 0, sizeof(ULL) * (p+2));

    ile[i] = new short int[p+2];
    memset(ile[i], 0, sizeof(short int) * (p+2));
    }

  FOR(i, 2, n)par[i].s = byl_cost[par[i].s];
  FOR(i, 1, p)coeff[i] = R(1, 1e13); 

  FOR(i, 2, n)
    {
    FOR(j, 1, p)
      {
      ile[i][j] = ile[par[i].f][j];
      }
    ile[i][par[i].s]++;

    FORD(j, p, 1)
      {
      h[i][j] = h[i][j+1] + ile[i][j] * coeff[j];
      }
    }

  FOR(i, 1, n)FOR(j, 1, i-1)B[i][j] = 1;

  if(p <= 40)
 // if(p <= 10)
    {
    go_small_p(k, p);
    }
  else go(k);
  }