Mirror IIOT 2022-2023, International Round | tourdetree

In the distant future the organizers of Tour de France have relocated the competition to Treeland. Treeland consists of $N$ cities, numbered from $1$ to $N$, and $N-1$ bidirectional roads numbered from $1$ to $N-1$. Road $i$ connects city $a_i$ to city $b_i$ and has length $c_i$. It's possible to reach every city from every other city using these roads. Due to strange socio-economical factors the cities with only one road adjacent to them have become metropolises.

The rules of the competition are the following:

• The cyclists start from a metropolis chosen by the organizers.
• They visit all cities using the roads in some way. They may visit the same city and use the same road multiple times.
• They finish in a metropolis chosen by the organizers.

The organizers choose $K$ metropolises, where $K$ is either $1$ or $2$. If $K=1$, then the chosen metropolis is used to start as well as to finish the race.
If $K=2$, then two different metropolises are chosen, one of them serving as the start, the other as the finish of the race.

Given the map of Treeland and the value of $K$, what is the minimum total length of the roads the cyclists have to cycle through
from start to finish, if both the organizers and the cyclists want to minimize this sum?

Input data

The first line contains two integers $N$ and $K$. The next $N-1$ lines contains three integers each, the numbers $a_i$, $b_i$ and $c_i$ for road $i$.

Output data

You need to write a single line with an integer: the minimal sum of road lengths that the cyclists need to traverse.

Constraints and Clarifications

• $2 \le N \le 100 \ 000$.
• $1 \le K \le 2$.
• $1 \le a_i \neq b_i \le N$ for each $i=1\ldots N-1$.
• $1 \le c_i \le 1 \ 000 \ 000 \ 000$ for each $i=1\ldots N-1$.

Example 1

stdin

3 1
1 2 4
2 3 5

stdout

18

Explanation

In the first sample case the value of $K$ is $1$. Choosing the metropolis with index $1$ results in the cyclists taking the path $1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1$ which has a length of $4+5+5+4=18$.

Example 2

stdin

4 2
1 2 10
2 3 10
2 4 11

stdout

41

Explanation

In the second sample case $K=2$, and it is optimal to choose metropolises $1$ and $4$.