406251: GYM102331 A Apollonian Network
Description
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?
InputThe 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.
OutputOutput one integer: the largest sum of edge weights on a simple path in Yuhao's Apollonian network.
ExamplesInput3 1 2 1 2 3 1 3 1 2Output
3Input
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 3Output
35Note
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$$$.