Cutting the Rooted Tree

In this problem, you are given a rooted tree with n nodes. The tree is rooted at node 1 and every edge has a cutting cost. The goal is to remove a set of edges with minimum total cost so that no leaf node remains connected to the root. A leaf is defined as a node with no children. In other words, after cutting the selected edges, there should be no path from the root to any leaf node.

This problem can be approached via a recursive strategy (dynamic programming on trees). For each node u with children v, let \( f(u) = \sum_{v \in children(u)} \min\big(c(u,v), f(v)\big) \) where \( c(u,v) \) is the cost to cut the edge between \( u \) and \( v \). Notice that for a leaf node (except possibly the root if it is the only node), we set \( f(leaf) = +\infty \) to force cutting the edge connecting it to its parent.

inputFormat

The input begins with an integer n representing the number of nodes in the tree. The nodes are numbered from 1 to n, and node 1 is always the root. Each of the next n-1 lines contains three integers u, v, and w, indicating there is an edge from node u to node v with a cutting cost of w.

outputFormat

Output a single integer representing the minimum total cost required to cut the tree so that no leaf node is connected to the root.

sample

3
1 2 3
1 3 4

7