Apollonian Network

Time limit3sMemory limit512 MB

Summary

Given a weighted Apollonian network with n vertices, find the largest total edge weight of any simple path in the graph.

Level: Hard9 of 10
Topics: Graph, Dynamic programming, Recursion
Solved: No attempts yet

Problem

An Apollonian network is an undirected graph. It starts from a triangle, and then repeatedly takes a triangle in the middle and splits it into three smaller triangles.

In a weighted Apollonian network, find the simple path with the largest total weight, and print that total weight.

Input

The first line contains the number of vertices $n$ ( $3 \le n \le 250$ ).

The next $3(n-2)$ lines each contain three integers $a_i$ , $b_i$ , $c_i$ . Each line means that an edge with weight $c_i$ connects vertices $a_i$ and $b_i$ . ( $1 \le a_i, b_i \le n$ , $0 \le c_i \le 10^6$ )

The given graph is an Apollonian network.

Output

Print the largest total weight of a simple path.

Examples2

Example 1
Input
```
3
1 2 1
2 3 1
3 1 2
```
Expected output
```
3
```

Example 2

Input

Expected output