#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define LL long longconst int N = 100007;const LL MOD = 100000007;int n,m;LL ans;LL C[20][20];LL D[N][11],F[N][11],G[N][11];struct Edge{ LL w; int t,next;} e[N<<2];int et,head[N];void addEdge(int s,int t,int w){ w=(w%MOD+MOD)%MOD; e[et].t=t,e[et].w=w,e[et].next=head[s],head[s]=et++; e[et].t=s,e[et].w=w,e[et].next=head[t],head[t]=et++;}void preCN(){ int i,j; for(i=0;i<20;++i){ C[i][0]=C[i][i]=1; for(j=1;j<i;++j){ C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD; } }}void dfs1(int u,int p=-1){ LL w; int v,i,j,k; for(i=0;i<=m;++i) D[u][i]=0; for(i=head[u];i!=-1;i=e[i].next) if((v=e[i].t)!=p){ dfs1(v,u); for(j=0;j<=m;++j){ for(k=0,w=1;k<=j;++k,w=(w*e[i].w)%MOD){ D[u][j]=(D[u][j]+(C[j][k]*w)%MOD*D[v][j-k]%MOD)%MOD; } } } D[u][0]=(D[u][0]+(LL)1)%MOD;}void dfs2(int u,int p=-1){ LL w; int v,i,j,k; if(u) ans=min(ans,(F[u][m]+D[u][m])%MOD); for(i=head[u];i!=-1;i=e[i].next) if((v=e[i].t)!=p){ for(j=0;j<=m;++j) G[u][j]=(F[u][j]+D[u][j])%MOD; for(j=0;j<=m;++j){ for(k=0,w=1;k<=j;++k,w=(w*e[i].w)%MOD){ G[u][j]=((G[u][j]-(C[j][k]*w)%MOD*D[v][j-k]%MOD+MOD)%MOD+MOD)%MOD; } } for(j=0;j<=m;++j){ F[v][j]=0; for(k=0,w=1;k<=j;++k,w=(w*e[i].w)%MOD){ F[v][j]=(F[v][j]+(C[j][k]*w)%MOD*G[u][j-k]%MOD)%MOD; } } dfs2(v,u); }}int main(){ int i,u,v,w; preCN(); memset(F,0,sizeof(F)); while(~scanf("%d%d",&n,&m)){ et=0,memset(head,-1,sizeof(head)); for(i=1;i<n;++i){ scanf("%d%d%d",&u,&v,&w); addEdge(u,v,w); } if(m==0){ printf("%dn",n-1); continue; } dfs1(0); ans=D[0][m]; dfs2(0); printf("%lldn",ans); } return 0;}
