1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 using namespace std;  5 #define LL long long  6 int n,K;  7 const int maxn=210;  8 const LL inf=3000000000LL;  9 struct node{ 10     int y,next,v; 11 }e[maxn]; 12 int linkk[maxn],len=0,w[maxn],d[maxn][maxn],siz[maxn],q[maxn],tail=0,fa[maxn],ru[maxn],vis[maxn]; 13 int read(){ 14     int x=0;char ch=getchar();bool flag=0; 15     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)flag=1;ch=getchar();} 16     while(ch<=‘9‘&&ch>=‘0‘){x=x*10+ch-‘0‘;ch=getchar();} 17     return flag?-x:x; 18 } 19 void insert(int x,int y,int v){ 20     e[++len].y=y; 21     e[len].v=v; 22     e[len].next=linkk[x]; 23     linkk[x]=len; 24 } 25 void print(int x){printf("%d\n",x);} 26 void print(int x,int y){printf("%d %d\n",x,y);} 27 void init(){ 28     int y,v; 29     n=read(),K=read(); 30     memset(d,10,sizeof(d)); 31     for(int i=1;i<=n;i++){ 32         w[i]=read(),y=read(),v=read(); 33         insert(i,y,v);insert(y,i,v); 34         d[i][y]=v,d[y][i]=v; 35     } 36      37 } 38 void findd(){ 39     for(int i=1;i<=n;i++)d[i][i]=0; 40     for(int k=0;k<=n;k++) 41         for(int i=0;i<=n;i++) 42             for(int j=0;j<=n;j++) 43                 if(d[i][k]+d[k][j]<d[i][j])d[i][j]=d[i][k]+d[k][j]; 44 } 45 LL f[110][60][110]; 46 void dfs(int x,int f){ 47     siz[x]=1; 48     fa[x]=f; 49     for(int i=linkk[x];i;i=e[i].next){ 50         if(e[i].y==f)continue; 51         dfs(e[i].y,x); 52         siz[x]+=siz[e[i].y]; 53         ru[x]++; 54     } 55     if(siz[x]==1)q[++tail]=x; 56 } 57 void work(){ 58     memset(f,-1,sizeof(f)); 59     findd(); 60     dfs(0,0); 61     for(int head=1;head<=tail;head++){ 62         int x=q[head]; 63         ru[fa[x]]--; 64         if(ru[fa[x]]==0)q[++tail]=fa[x]; 65         LL g[56]; 66         for(int k=0;k<=siz[x]&&k<=K;k++){ 67             for(int prev=fa[x];prev!=-1;prev=fa[prev]){ 68                  69                 for(int p=0;p<=k;p++)g[p]=0; 70                 for(int i=linkk[x];i;i=e[i].next){ 71                     if(e[i].y==fa[x])continue; 72                     LL minn=inf; 73                     for(int j=k;j>=0;j--){ 74                         minn=inf; 75                         for(int l=0;l<=siz[e[i].y]&&l<=j;l++) 76                             minn=min(minn,g[j-l]+f[e[i].y][l][prev]); 77                         g[j]=minn; 78                     } 79                 } 80                 LL ans=g[k]+w[x]*d[prev][x]; 81                 for(int p=0;p<=k;p++)g[p]=0; 82                 for(int i=linkk[x];i;i=e[i].next){ 83                     if(e[i].y==fa[x])continue; 84                     LL minn=inf; 85                     for(int j=k-1;j>=0;j--){ 86                         minn=inf; 87                         for(int l=0;l<=siz[e[i].y]&&l<=j;l++) 88                             minn=min(minn,g[j-l]+f[e[i].y][l][x]); 89                         g[j]=minn; 90                     } 91                 } 92                 f[x][k][prev]=min(ans,k-1<0?inf:g[k-1]); 93                 if(!prev)break; 94             } 95         } 96     } 97     cout<<f[0][K][0]<<endl; 98 } 99 int main(){100     freopen("1.in","r",stdin);101     freopen("1.out","w",stdout);102     init();103     work();104 }