题目描述

给定一棵 $n$ 个点的树，你可以选择若干条长度恰好为 $4$ 的不交链，可以不选。

方案的收益定义为选出的链的并集的边权和，求最大收益。

输入格式
第一行一个正整数 $n$，表示树的节点数。

第二行至第 $n$ 行，每行三个整数 $u$，$v$，$w$，表示 $u$ 和 $v$ 之间有边相连，边权为 $w$。

保证输入的是一棵树。

输出格式
一行一个整数 $ans$，表示最大收益。

样例 1
输入

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

最优解为 $57$。

链 $2 \sim 6$，权值为 $2$；
链 $6 \sim 10$，权值为 $50$；
链 $11 \sim 15$，权值为 $3$；
链 $16 \sim 19$，权值为 $2$。

样例 2
输入

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

输出

0

容易发现，每一条长度为 $4$ 的链权值均为负数。

数据范围与提示
$2 \leq n \leq 200000$
$-10^9 \leq a_i \leq 10^9$