给定一棵树，每条边都有一个非负整数权值。

令 $d(u, v)$ 为顶点 $u$ 和 $v$ 之间唯一简单路径上所有边权的最大值。

在所有顶点 $p_1, p_2, \dots, p_n$ 的排列中，求 $\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$ 的最大值。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 100\,000$)：树的顶点数。

接下来的 $n-1$ 行，每行包含三个整数 $u, v, w$ ($1 \le u, v \le n, 0 \le w \le 30$)，表示树中一条连接顶点 $u$ 和 $v$ 且权值为 $w$ 的边。

输出格式

输出一个整数：$\sum_{i=2}^{n} 2^{d(p_{i-1}, p_i)}$ 的最大值。

样例

输入格式 1

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

输出格式 1

6

说明

在第一个样例中，其中一个最优排列是 $\{4, 5, 3, 2, 1\}$。

输入格式 2

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

输出格式 2

42