Apollonian 网络是一种通过递归地将三角形细分为三个更小的三角形而形成的无向图。

Yuhao Du 拥有一个带权边的 Apollonian 网络。他知道如何找到权值之和最大的简单路径。你能找到它吗？

输入格式

第一行包含一个整数 $n$：Yuhao 的 Apollonian 网络中的顶点数 ($3 \le n \le 250$)。

接下来的 $3(n - 2)$ 行包含图的边描述。每行包含三个整数 $a_i, b_i, c_i$，描述了顶点 $a_i$ 和 $b_i$ 之间的一条权值为 $c_i$ 的边 ($1 \le a_i, b_i \le n, a_i \neq b_i, 0 \le c_i \le 10^6$)。

保证给定的图是一个 Apollonian 网络。

输出格式

输出一个整数：Yuhao 的 Apollonian 网络中简单路径上的最大边权和。

样例

输入 1

3
1 2 1
2 3 1
3 1 2

输出 1

3

输入 2

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

输出 2

35

说明

在第一个样例中，其中一条最优路径是 $2 \to 3 \to 1$。

在第二个样例中，其中一条最优路径是 $5 \to 2 \to 1 \to 7 \to 10 \to 8 \to 9 \to 3 \to 6 \to 4$。