406251: GYM102331 A Apollonian Network

An Apollonian network is an undirected graph formed by recursively subdividing a triangle into three smaller triangles.

Yuhao Du has an Apollonian network with weighted edges. And he knows how to find a simple path with the largest possible sum of edge weights. Can you find it too?

The first line of the input contains one integer $$$n$$$: the number of vertices in Yuhao's Apollonian network ($$$3 \leq n \leq 250$$$).

The next $$$3(n-2)$$$ lines contain a description of the edges of the graph. Each of these lines contains three integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, describing an edge between vertices $$$a_i$$$ and $$$b_i$$$ with weight $$$c_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$, $$$0 \leq c_i \leq 10^{6}$$$).

It is guaranteed that the given graph is an Apollonian network.

Output one integer: the largest sum of edge weights on a simple path in Yuhao's Apollonian network.

3
1 2 1
2 3 1
3 1 2

3

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

35

In the first example, one of the optimal paths is $$$2 \to 3 \to 1$$$.

In the second example, one of the optimal paths is $$$5 \to 2 \to 1 \to 7 \to 10 \to 8 \to 9 \to 3 \to 6 \to 4$$$.