In the year 11328, scientists from country C developed a high-speed transport tunnel system that can transport residents from one end of a tunnel to the other in a very short time. These tunnels are bidirectional.

The drawback is that these transport tunnels require a significant amount of maintenance and inspection. After planning, the President of country C decided to build this type of tunnel in city M, establishing $n$ transport stations and $3 \times (n - 1)$ transport tunnels. These tunnels are divided into 3 groups, each containing $(n - 1)$ tunnels.

When any group of tunnels is in operation, residents can travel from any transport station to any other transport station using this group of tunnels. In other words, all transport stations are connected by the tunnels.

The three groups of tunnels operate in a rotating sequence of 1, 2, 3, repeating cyclically. At any given moment, only one group of transport tunnels is available for use. Formally, on day $i$, only the $((i - 1) \pmod 3 + 1)$-th group of tunnels is in operation.

A famous scientist from country C, Access Globe, is conducting a social survey experiment: investigating the information of users of the transport tunnels between two transport stations. Access Globe's plan is as follows:

• Select two transport stations $a$ and $b$.
• On the first day, he starts from $a$, uses the currently operating group of tunnels to reach $b$ along the shortest path, and investigates the information of users on all tunnels passed.
• On the second day, he starts from $b$, uses the currently operating group of tunnels to reach $a$ along the shortest path, and investigates the information of users on all tunnels passed.
• On the third day, he starts from $a$, uses the currently operating group of tunnels to reach $b$ along the shortest path, and investigates the information of users on all tunnels passed.

Access Globe knows the number of users for each transport line when it is in operation. He hopes to find a pair $a, b$ such that the sum of the number of users on all tunnels passed during the entire experiment is maximized. Access Globe hopes that you, as a participant in CCF NOI 2018 Winter Camp, can help him solve this simple little problem. If you successfully solve this problem, Access Globe will give you a small gift—100 points!

Input

Read the data from the file tunnel.in.

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

The 2nd to $n$-th lines of the input file each contain 3 numbers $u, v, w$, representing a tunnel in the first group connecting $u$ and $v$, with $w$ users when it is in operation.

The $(n + 1)$-th to $(2n - 1)$-th lines of the input file each contain 3 numbers $u, v, w$, representing a tunnel in the second group connecting $u$ and $v$, with $w$ users when it is in operation.

The $2n$-th to $(3n - 2)$-th lines of the input file each contain 3 numbers $u, v, w$, representing a tunnel in the third group connecting $u$ and $v$, with $w$ users when it is in operation.

Output

Output to the file tunnel.out.

The output file contains 1 line with a single integer, representing the maximum sum of the number of users.

Examples

Input 1

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

Output 1

27

Note 1

See tunnel/tunnel1.in and tunnel/tunnel1.ans in the contestant's directory.

Explanation 1

The figure below shows the transport stations and transport lines in city M for the example. The lines alternating between dots and dashes, dashed lines, and solid lines represent the first, second, and third groups of tunnels, respectively.

A feasible plan is to choose $a = 2, b = 5$. The sum of the number of users is $(3) + (8 + 5 + 1) + (2 + 1 + 7) = 27$.

Examples

Input 2

(See tunnel/tunnel2.in in the contestant's directory)

Output 2

(See tunnel/tunnel2.ans in the contestant's directory)

Subtasks

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

• Special property 0: Any two groups of tunnels are completely identical.
• Special property 1: The second group of tunnels and the third group of tunnels are completely identical.
• Special property 2: For every transport station in the second group, at most two tunnels can reach it, and the necessary and sufficient condition for a direct connection between transport stations with labels $x$ and $y$ is $|x - y| = 1$.
• Special property 3: For every transport station in the third group, at most two tunnels can reach it.
• Special property 4: $n \le 3000$.

Note

• In two groups of tunnels, it is possible that both contain a tunnel connecting transport stations $x$ and $y$; in this case, we consider these two tunnels to be distinct.
• In the special properties, "completely identical" for group A tunnels and group B tunnels means: if there exists a tunnel between $u$ and $v$ with $w$ users in group A, then there must also exist a tunnel between $u$ and $v$ with $w$ users in group B. Whether they are identical is independent of the description method and description order. That is, in two completely identical groups of tunnels A and B, the input order of the tunnels is not necessarily the same, and the input order of the endpoints of each tunnel is not necessarily the same (for a tunnel connecting $u$ and $v$ with $w$ users in groups A and B, one possible input is: $u\ v\ w$ for group A, and $v\ u\ w$ for group B).