Problem Description

Given a tree with $n$ vertices, you may choose several pairwise disjoint paths of length $4$ (meaning $4$ edges) (you may also choose none).

For a chosen set of paths, the profit is the sum of edge weights in the union of all chosen paths. Find the maximum profit.

Input Format

The first line contains an integer $n$.

The next $n - 1$ lines each contain three integers $u, v, w$, describing an edge $(u, v)$ in the tree with weight $w$.

Output Format

Output one line with one integer, the required value.

19
1 2 1
2 3 2
3 4 -1
4 5 -1
5 6 2
6 7 11
7 8 12
8 9 13
9 10 14
11 12 3
12 13 0
13 14 0
14 15 0
15 16 1
16 4 0
4 17 0
17 18 0
18 19 2

57

6
1 2 2
2 3 -1
3 4 -1
4 5 -1
5 6 2

0

Hint

Explanation of Sample #1

One optimal solution is to choose the paths $2 \to 6$, $6 \to 10$, $11 \to 15$, $16 \to 19$.

Explanation of Sample #2

Since the weight of every length $4$ path is negative, choosing none is optimal.

Constraints

For $100\%$ of the testdata, $2 \leq n \leq 2 \times 10^5$, and $-10^9 \leq w_i \leq 10^9$.

Translated by ChatGPT 5