Description

In the year 11328, scientists in country C developed a high-speed teleportation channel that can send residents from one end to the other in a very short time. These channels are bidirectional.

The downside is that such channels require extensive maintenance and inspection. After planning, the president of country C decided to build such channels in City M. In City M, $n$ teleportation stations and $3 \times (n-1)$ channels were built. These channels are divided into $3$ groups, each containing $(n-1)$ channels.

When any one group of channels is operating, residents can travel via this group of channels from any station to any other station. In other words, all stations are connected by channels.

The three groups of channels operate in a round-robin fashion in the order $1$, $2$, $3$, repeatedly. At any moment, exactly one group of channels is available. Formally, on day $i$, only group $((i-1)\bmod 3+1)$ is operating.

The renowned scientist Access Globe is conducting a social survey experiment: collecting information on users of the channels between two stations. Access Globe’s plan is as follows:

• Choose two stations $a, b$.
• On day one, he starts from $a$, uses the currently operating group of channels to reach $b$ along a shortest path, and surveys the users on all channels he traverses.
• On day two, he starts from $b$, uses the currently operating group of channels to reach $a$ along a shortest path, and surveys the users on all channels he traverses.
• On day three, he starts from $a$, uses the currently operating group of channels to reach $b$ along a shortest path, and surveys the users on all channels he traverses.

Access Globe knows the number of users on each channel when it is operating. He wants to find a pair $a, b$ such that the total number of users over all traversed channels during the entire experiment is maximized.

Access Globe hopes you, a participant of the CCF NOI 2018 Winter Camp, can help him solve this simple problem. If you succeed, Access Globe will give you a small gift — $100$ points.

Input Format

The first line contains a positive integer $n$, the number of stations, numbered from $1$ to $n$.

Lines $2$ to $n$: each line contains three numbers $u, v, w$, indicating that in the first group there is a channel connecting $u$ and $v$, with $w$ users when it is operating.

Lines $(n+1)$ to $(2n-1)$: each line contains three numbers $u, v, w$, indicating that in the second group there is a channel connecting $u$ and $v$, with $w$ users when it is operating.

Lines $2n$ to $(3n-2)$: each line contains three numbers $u, v, w$, indicating that in the third group there is a channel connecting $u$ and $v$, with $w$ users when it is operating.

Output Format

Output a single line containing an integer: the maximum possible sum of user counts.

5
1 2 2
1 3 0
1 4 1
4 5 7
1 2 0
2 3 1
2 4 1
2 5 3
1 5 2
2 3 8
3 4 5
4 5 1

27

Hint

[Sample 1 Explanation]

The figure below shows the stations and channels in City $M$ for the sample. The alternating dotted-and-dashed lines, dotted lines, and solid lines denote the first, second, and third groups of channels, respectively. One feasible plan is to choose $a=2, b=5$. The total number of users is $(3) + (8+5+1) + (2+1+7) = 27$.

[Subtasks]

Constraints:

• For all testdata, $2 \le n \le 10^5$, $0 \le w \le 10^{12}$.

Special properties:

• Special property $0$: Any two groups of channels are structurally identical.
• Special property $1$: The second and third groups of channels are structurally identical.
• Special property $2$: In the second group, each station has degree at most $2$, and stations numbered $x, y$ are directly connected by a channel if and only if $|x-y|=1$.
• Special property $3$: In the third group, each station has degree at most $2$.
• Special property $4$: $n \le 3000$.

There are $31$ test points in total, with the following mapping from subtasks to test points:

• Subtask $0$: test points $1$–$7$.
• Subtask $1$: test point $8$.
• Subtask $2$: test points $9$–$11$.
• Subtask $3$: test points $12$–$14$.
• Subtask $4$: test points $15$–$17$.
• Subtask $5$: test points $18$–$21$.
• Subtask $6$: test points $22$–$25$.
• Subtask $7$: test points $26$–$31$.

[Notes]

• It is possible that two groups both contain a channel connecting stations $x$ and $y$. In that case, we consider these as two distinct channels.
• In the special properties, “structurally identical” between groups A and B means: if there is a channel between $u$ and $v$ with user count $w$ in group A, then there must also be a channel between $u$ and $v$ with user count $w$ in group B. Whether they are considered identical is independent of the description format and the input order. That is, in two structurally identical groups A and B, the order of channel inputs may differ, and the order of endpoints in each channel’s input may also differ (for a channel connecting $u, v$ with user count $w$ in groups A and B, one possible input is $u\ v\ w$ for group A and $v\ u\ w$ for group B).

Translated by ChatGPT 5