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
The first robot's route is , and the rest two stay at root.