矮人们刚刚建成了他们新的地下村庄。现在是时候规划在其中运行的铁路网了。

村庄由 $N$ 个交叉路口和连接它们的 $N - 1$ 条隧道组成。隧道的建造方式保证了从任何一个交叉路口都可以到达其他任何一个交叉路口。在每一个死胡同（即仅由一条隧道连接的交叉路口）处，都有一个火车站。

你的任务是确定村庄中火车的路线。为了满足矮人们的要求，所有的车站必须两两配对（幸运的是，车站总数是偶数），并且每一对车站之间将有一列火车运行，使用它们之间最短的路径。然而，隧道有其局限性。尽管每条隧道的长度相同（均为 1），但它们的宽度限制了可以通过该隧道的路线数量。

矮人们希望所有火车路线的总长度尽可能长。你能计算出最大总长度是多少吗？

输入格式

输入的第一行包含一个整数 $N$，表示村庄中交叉路口的数量。

接下来的 $N - 1$ 行，每行包含三个整数 $a_i, b_i, c_i$，表示在交叉路口 $a_i$ 和 $b_i$ 之间有一条隧道。值 $c_i$ 是可以通过该隧道的路线数量的上限。

输出格式

在第一行也是唯一一行中，输出一个整数，表示所选车站配对之间路径的最大总长度。

如果无法在满足约束条件的情况下对所有车站进行配对，则输出 -1。

数据范围

$2 \le N \le 200\,000$，$1 \le a_i, b_i \le N$，$0 \le c_i \le N$，所有交叉路口均连通，且车站（即死胡同）的数量为偶数。

样例

输入 1

10
1 2 2
2 3 1
3 4 3
5 1 1
6 1 2
7 2 3
8 3 2
9 3 1
10 4 7

输出 1

10

输入 2

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

输出 2

-1

说明 1

在第一个样例中，连接交叉路口 5–9、6–7 和 8–10 的车站，得到的火车路线总长度为 $4 + 3 + 3 = 10$。