题目描述

给定一棵有向树$\red {T}$，树$\red {T}$ 中每个顶点$\red {u}$都有一个权$\red {w(u)}$；树的每条边$\red {(u,v)}$也都有一个非负边长$\red {d(u,v)}$。有向树$\red {T}$的每个顶点$\red {u}$ 可以看作客户，其服务需求量为$\red {w(u)}$。每条边$\red {(u,v)}$的边长$\red {d(u,v)}$ 可以看作运输费用。如果在顶点$\red {u }$处未设置服务机构，则将顶点$\red {u }$处的服务需求沿有向树的边$\red {(u,v)}$转移到顶点$\red {v}$ 处服务机构需付出的服务转移费用为$\red {w(u)\times d(u,v)}$。树根处已设置了服务机构，现在要在树$\red T$中增设$\red {k}$处服务机构，使得整棵树$\red T$ 的服务转移费用最小。 对于给定的有向树$\red {T}$，编程计算在树$\red {T}$中增设$\red {k}$处服务机构的最小服务转移费用。

输入格式

第$\red {1}$行有$\red {2}$个正整数$\red {n}$和$\red {k}$。$\red {n}$表示有向树$\red {T}$ 的边数；$\red {k}$是要增设的服务机构数。有向树$\red {T }$的顶点编号为$\red {0，1，…，n}$。根结点编号为$\red {0}$。接下来的$\red {n}$行中，每行有表示有向树$\red {T}$的一条有向边的$\red {3}$个整数。第$\red {i+1}$行的$\red {3 }$个整数$\red {w_i,v_i,d_i}$分别表示编号为$\red {i }$的顶点的权为$\red {w_i}$，相应的有向边为$\red {(i, v_i)}$，其边长为$\red {d_i}$。

输出格式

将计算的最小服务转移费用输出到文件 。

样例

输入样例

4 2

1 0 1

1 1 10

10 2 5

1 2 3

输入样例

4