Description

从前有棵树。

找出K个点A1，A2，…，Ak。

使得∑dis(AiAi+1),(1<=i<=K-1)最小。

Format

Input

第一行两个正整数n,k,表示数的顶点数和需要选出的点个数。

接下来n-l行每行3个非负整数x,y,z，表示从存在一条从x到y权值为z的边。

I<=k<=n。

l<x,y<=n

1<=z<=10^5

n <= 3000

Output

一行一个整数，表示最小的距离和。

Samples

10 7
1 2 35129
2 3 42976
3 4 24497
2 5 83165
1 6 4748
5 7 38311
4 8 70052
3 9 3561
8 10 80238

184524