Agamemnon's Odyssey

Example map

Agamemnon, the great king of Mycenae, was assembling his troops in Aulis to sail to the shores of Troy, when he had a vision of goddess Artemis. In this vision, Agamemnon found out that he had accidentally slain a deer that was sacred to Artemis, and now the goddess swore to make Agamemnon suffer on his voyage to Troy.

Along his route to Troy, Agamemnon was planning to stop at the islands of Crete to gather resources for his formidable army. If Artemis were to find out about the sea routes Agamemnon took, she would use her powers to stop the wind along those routes, leaving Agamemnon and his crew stranded. As the trusty advisor of Agamemnon, you now have to help him devise a path between the islands of Crete that provides the army the maximum amount of resources, without letting Artemis discover the routes you take.

The $N$ islands of Crete are connected to each other via $N-1$ sea routes. Along each route, Agamemnon can acquire a certain amount of resources. However, if a route is used more than $k$ times, Artemis will detect the presence of Agamemnon along that route and stop the wind along that route. So, a feasible plan cannot use any route more than $k$ times.

Given that Agamemnon can start and end at any of the islands of Crete, come up with a feasible plan that maximises Agamemnon's resource earnings. Note that Agamemnon can only collect resources along a sea route during its first use. He does not earn extra resources from a route on reusing it.

The first line of input will contain two integers, $N$ ($1 \leq N \leq 2 \cdot 10^5$) and $k$ ($1 \leq k \leq 10^9$), the number of islands of Crete, and the maximum number of times a single route may be used without being discovered by Artemis. The islands of Crete are guaranteed to be connected by the sea routes.

The following $N-1$ lines describe the sea routes. Each line contains $3$ integers each, $u, v$ ($1 \leq u, v \leq N, u \neq v$) and $c$ ($1 \leq c \leq 10^9$), explaining that the sea route connects islands $u$ and $v$ and Agamemnon can acquire $c$ units of resources along this route. All sea routes are bidirectional, i.e. they can be used to travel from island $u$ to $v$, or from island $v$ to $u$.

Output a single value, the maximum amount of resources Agamemnon can acquire with a feasible plan, as described in the statement.

There are $5$ islands in Crete, connected to each other via $4$ routes, as shown in the figure: the first connecting island $1$ and $2$ and allowing Agamemnon to acquire $3$ units of resources and so on. In this archipelago, the best plan for Agamemnon is to start at island $4$, visit island $1$ (acquiring $5$ units of resources along the $4\to1$ route), and then end his path at island $5$ (acquiring another $9$ units of resources along the $1\to5$ route), having earned a total of $14$ units of resources.