Problem G: NO Intersections Plz

## Problem G: NO Intersections Plz

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 190  Solved: 47
[Submit][Status][Web Board]

## Description

Given a weighted tree with $$N$$ nodes. The distance of a simple path is defined as the sum of all edges in the path. You should choose $$M$$ simple paths with no edge intersection between any two paths (But two paths can intersect at certain nodes). Now you are asked to calculate the maximum distance of the shortest path.

## Input

The first line contains two integers $$N$$ and $$M(1\leq M< N\leq 5\times 10^4)$$

The next $$n-1$$ lines each contain three integers $$x,y,w$$, denoting there is an edge with weight $$w$$ connecting $$x$$ and $$y(1\leq x,y\leq N,1\leq w\leq 10^4)$$

## Output

Output one single integer, indicating the maximum distance of the shortest path.

## Sample Input

7 1
1 2 10
1 3 5
2 4 9
2 5 8
3 6 6
3 7 7

## Sample Output

31

[Submit][Status]