1139C - Edgy Trees - CodeForces Solution

//......................................// Work hard in silence, let the success make the noise //..............................//
//.....................................................//THINK TWICE .. CODE ONCE//.............................................//
#include<bits/stdc++.h> 
#define improve ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);  
#define ll long long 
#define ld long double
#define dv vector<ll> 
#define dvp vector<pair<ll,ll>> 
#define dit vector<ll>::iterator 
#define dvv vector<vector<ll>>
#define dvb vector<bool>
#define dm map<ll,ll>
#define ds set<ll>
#define loop(n) for (ll i = 0; i < n; i++)
#define loopj(n) for (ll j = 0; j < n; j++)
#define loopit(v) for (auto it = v.begin(); it != v.end(); ++it)
#define input(n,v) loop(n) { ll in; cin >> in; v.push_back(in);} 
#define inputvp(n,v) loop(n) {ll x,y; cin>>x>>y; v.push_back(make_pair(x,y));}
#define prefix_sum(n,v,s) loop(n) { s[i] = v[i]; if (i)s[i] += s[i - 1]; }
#define suffix_sum(n,v,s) reverse(all(v)); prefix_sum(n, v, s) reverse(all(s))
#define all(v) v.begin(), v.end()
#define bs(v,n) binary_search(all(v), n)
#define lb(v,x) lower_bound(all(v), x) - v.begin()
#define ub(v,x) upper_bound(all(v), x) - v.begin()
#define fix(n, res) fixed <<  setprecision(n) << (ld)res
#define posmod(n,m) ((n % m)+ m) % m
#define chk(ret) for (auto& v : ret)cout << v <<" "; cout<<"\n"
#define chkvp(ret) for (auto& v : ret)cout << v.first<<" "<< v.second << "\n";
#define chkmp(m)  for (auto const &pair: m) cout << "{" << pair.first << " : " << pair.second << "}\n"
#define chkmpv(m)     for(auto const &m: mp){cout << m.first << " : ";for (auto const &s : m.se)  cout << s << " ";cout << "\n"; }
#define sz(s) s.size() 
#define pb push_back
#define  EPS = 1e-10
#define fi first
#define se second  
#define pi 3.14159265358979323 
using namespace std;
const ll MOD = 1e9 + 7, N = 1e6 + 5, MAX = 500;

dv par(N, 0);
dv s(N, 1);
ll find_parent(ll u)
{
    if (par[u] == u)return u;
    else return par[u] = find_parent(par[u]);
}
bool is_con(ll u, ll v)
{
    u = find_parent(u);
    v = find_parent(v);
    return (u == v);
}
void con(ll u, ll v)
{
    if (is_con(u, v))return;
    u = find_parent(u);
    v = find_parent(v); 
    if (s[u] < s[v])
    { 
        par[u] = v;
        s[v] += s[u];
    }
    else
    { 
        par[v] = u;
        s[u] += s[v];
    }
}
ll int binpow(ll int a, ll int b, ll int m) {
    a %= m;
    ll int res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int main()
{
    improve;
    loop(N)par[i] = i;
    ll n = 0, k = 0; cin >> n >> k;
    loop(n - 1)
    {
        ll u = 0, v = 0, c = 0; cin >> u >> v >> c; 
        u--, v--;
        if (!c)con(u, v);
    }  
    set<ll>st;
    loop(n) 
        st.insert(find_parent(par[i])); 
    ll cnt = 0;
    for (auto i : st)
    {
        cnt = (cnt+ binpow(s[i], k, MOD))%MOD ; 
       
    }
    cout << (binpow(n, k, MOD) - cnt + MOD) % MOD;

}