题目描述

小蓝需要一些木材来装修他的新房子，他找来了一棵有 $n$ 个结点的树，每条边有一个权值。他想要在树上砍下一些木材，每根木材由一条边和其两端的结点构成，其权值为这条边的权值，所以一个结点最多属于一根木材。小蓝想知道，在树上砍下的木材的权值和最大是多少？

输入格式

输入的第一行包含一个正整数 $n$。

接下来 $n−1$ 行，第 $i$ 行包含三个整数 $u_i,v_i,w_i$ ，相邻整数之间使用一个空格分隔，表示结点 $u_i$ 和 $v_i$ 之间有一条权值为 $w_i$ 的边。

输出格式

输出一行包含一个整数表示答案。

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

9

解释 #1

选择第 $2,4$ 条边作为木材，边权值和为 $5+4=9$。

数据范围

• 对于 $20\%$ 的评测用例，输入的树是一条链;

• 对于所有评测用例，$1≤n≤10^6$，$1≤u_i,v_i,w_i≤n$。