Maximum Weighted Disjoint Chains in a Tree

You are given a tree with n nodes. Each edge of the tree has an integer weight. A chain is defined as a simple path containing exactly 4 edges (and thus 5 vertices). You are allowed to select an arbitrary number (possibly zero) of chains in the tree under the restriction that no two selected chains share an edge. The benefit (or profit) of a selection is the sum of the weights of all edges that appear in at least one selected chain. Your task is to compute the maximum possible benefit.

More formally, let a chain be a sequence of vertices \(v_1, v_2, v_3, v_4, v_5\) such that for every \(i=1,2,3,4\) there is an edge between \(v_i\) and \(v_{i+1}\) in the tree. If you select several such chains \(C_1, C_2, \dots, C_k\) with the property that for any two distinct chains, their corresponding sets of edges are disjoint, then the score is given by:

$$ \text{score} = \sum_{e \in \bigcup_{i=1}^{k} C_i} w(e), $$

where \(w(e)\) denotes the weight of edge \(e\). Determine the maximum score you can obtain.

Note: A chain is said to be of length 4 if it contains exactly 4 edges. It is allowed to select no chain at all (in which case the score is 0).

inputFormat

The input begins with a line containing a single integer n — the number of nodes in the tree. The nodes are numbered from 1 to n. Each of the next n - 1 lines contains three space‐separated integers u v w indicating that there is an edge between nodes u and v with weight w.

outputFormat

Output a single integer — the maximum achievable score by selecting a set of disjoint chains of length 4.

sample

5
1 2 1
2 3 2
3 4 3
4 5 4

10