Tree and robots

4.7

3 votes
Tree, Dynamic Programming, Algorithms, Medium
問題

Given an undirected tree with vertices. Each edge  has a cost . The root of the tree is 1.

You have robots, each robot starts at root, walks through edges, finally stops at any vertex. When a robot travels through an edge , you will pay .

You need to make each edge to be visited by at least one robot (can be more than one robot).

Your goal is minimize the cost.

Input

The first line contains two integers, and .

In the next  lines, each line contains three integers, , means an edge  exists, and the cost is .

It's guaranteed that the given graph is a tree.

Output

An integer representing the minimum cost.

Constraints

サンプル入力
5 3
1 2 8
2 3 3
3 4 14
3 5 7
サンプル出力
39
実行速度: 2
メモリ制限: 256
ソース制限:
説明

The first robot's route is , and the rest two stay at root.

Contributers:
Editor Image

?