由于 SPLAY-CRT-2 病毒带来的医疗支出，拜特格勒（Bajtocjanie 的首都）的国库已经空空如也。再过四天，资金就会耗尽，城市将面临断电。很难想象在这种情况下会发生怎样的混乱——因此绝不能让这种情况发生！必须尽快征收新税以填补预算漏洞。

拜特格勒由 $n$ 个环形路口组成，编号从 $1$ 到 $n$，并由 $n-1$ 条街道连接。从任何一个路口都可以通过街道到达其他任何路口。特别地，有些路口只连接了一条街道（因此不难猜出，在如此管理不善的情况下，城市国库为何空虚）。

每条街道旁都住着拜特格勒人，他们准备贡献自己的钱财来拯救城市。对于每条街道，都估算出了从中征税的潜在收益。某些街道的收益可能是负数，因为已经扣除了各种征税成本——例如与设备和税务员酬金相关的费用。

每位受雇的税务员将从一个路口开始工作，并在接下来的四天内征税。每天，税务员能够沿着一条街道征税，并从该街道的一端走到另一端。在接下来的每一天，税务员将在前一天工作结束的路口所连接的其余街道中选择一条进行征税。由于财政状况极其严峻，税务员必须连续工作四天！因此，每位员工在此期间将从位于拜特格勒某两个路口之间路径上的恰好四条街道中征收税款。此外，为了避免社会动荡，规定任何街道的税款不得被重复征收。

请帮助拜特格勒当局计算通过这种方式可以获得的最大税收收益。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)，表示拜特格勒的路口数量。 接下来的 $n-1$ 行，每行描述一条街道；第 $i$ 行包含三个整数 $u_i, v_i, z_i$ ($1 \le u_i, v_i \le n, -10^9 \le z_i \le 10^9$)，表示路口 $u_i$ 和 $v_i$ 由一条街道连接，从该街道征税可获得 $z_i$ 巴伊塔拉（bajtalar）的收益。

输出格式

输出一行一个整数，表示通过征税获得的最大收益（单位为巴伊塔拉）。

样例

输入 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

输出 1

57

输入 2

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

输出 2

0

说明

在第一个测试用例中，最优策略是雇佣 4 名税务员，他们分别走过以下路径： 路口 2 和 6 之间，收益 2 巴伊塔拉； 路口 6 和 10 之间，收益 50 巴伊塔拉； 路口 11 和 15 之间，收益 3 巴伊塔拉； 路口 16 和 19 之间，收益 2 巴伊塔拉。

在第二个测试用例中，任何潜在的税务员路径都会带来亏损。因此，不雇佣任何人是最优的。