tourdetree

Time limit: 1s Memory limit: 256MB Input: Output:

In the distant future the organizers of Tour de France have relocated the competition to Treeland. Treeland consists of NN cities, numbered from 11 to NN, and N1N-1 bidirectional roads numbered from 11 to N1N-1. Road ii connects city aia_i to city bib_i and has length cic_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 KK metropolises, where KK is either 11 or 22. If K=1K=1, then the chosen metropolis is used to start as well as to finish the race.
If K=2K=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 KK, 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 NN and KK. The next N1N-1 lines contains three integers each, the numbers aia_i, bib_i and cic_i for road ii.

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

  • 2N100 0002 \le N \le 100 \ 000.
  • 1K21 \le K \le 2.
  • 1aibiN1 \le a_i \neq b_i \le N for each i=1N1i=1\ldots N-1.
  • 1ci1 000 000 0001 \le c_i \le 1 \ 000 \ 000 \ 000 for each i=1N1i=1\ldots N-1.
# Score Restrictions
1 0 Examples.
2 20 N300N \le 300 and ci106c_i \leq 10^6.
3 30 N2 000N \le 2 \ 000 and ci106c_i \leq 10^6.
4 50 No additional limitations.

Example 1

stdin

3 1
1 2 4
2 3 5

stdout

18

Explanation

In the first sample case the value of KK is 11. Choosing the metropolis with index 11 results in the cyclists taking the path 123211 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 1 which has a length of 4+5+5+4=184+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=2K=2, and it is optimal to choose metropolises 11 and 44.

Log in or sign up to be able to send submissions!