Problem 14

#include <vector>
#include <iostream>
#define int long long
#define mod 1000000007
using namespace std;
int p[100010],size[100010];
vector<int> v;
int find(int x){
    return (p[x]==x)?x:p[x]=find(p[x]);
}
inline void join(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    if(size[x]>size[y])
        swap(x,y);
    p[x]=y;
    size[y]+=size[x];
}
signed main() {
    int n,k,a,b,c,ans=0,abc[110]={1};
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        p[i]=i;
        size[i]=1;
    }
    for(int i=1;i<n;i++){
        cin>>a>>b>>c;
        if(!c){
            join(a,b);
        }
    }
    for(int i=1;i<=n;i++){
        if(p[i]==i){
            v.push_back(size[i]);
        }
    }
    for(int i=1;i<=k;i++)
        abc[i]=abc[i-1]*n%mod;
    for(auto &i:v){
        b=1;
        for(int j=1;j<k;j++){
            b=b*i%mod;
            ans=(ans+b*(n-i)%mod*abc[k-j-1])%mod;
        }
    }
    cout<<ans;
}