Maximizing Teleportation Channel User Counts

In the year 11328, scientists in Country C developed a high‐speed teleportation channel system that can instantly transport residents from one end of a channel to the other. However, due to heavy maintenance and repair requirements, the President of Country C decided to build one in City M. In City M, there are n teleportation stations and 3\times(n-1) bidirectional teleportation channels. These channels are divided into 3 groups and each group contains exactly n-1 channels. In every group, the stations are connected; that is, for any two stations, there is a unique simple path between them (i.e. the group forms a tree).

The three groups operate in rotation. On day i, only the group numbered \( ((i-1) \bmod 3 + 1) \) is active. Scientist Access Globe is conducting a study on the users of these channels. His plan is as follows:

• Select two stations \(a\) and \(b\).
• On Day 1, starting from \(a\), use the active (group 1) channels to travel on the unique shortest path (in the tree) to \(b\), and record the number of users on every channel passed.
• On Day 2, starting from \(b\), use the active (group 2) channels to travel on the shortest path back to \(a\) and record the usage numbers.
• On Day 3, starting from \(a\) again, use the active (group 3) channels to travel to \(b\) and record the usage numbers.

Every channel has a fixed number of users when it is running. The total number of users investigated is the sum of the users on all channels used during the three days, which is: \[ D(a,b)=d_1(a,b)+d_2(a,b)+d_3(a,b), \] where \(d_i(a,b)\) is the sum of the weights (usage counts) on the unique path from \(a\) to \(b\) in the i^th tree.

Your task is to help Access Globe find a pair of stations \(a\) and \(b\) that maximizes \(D(a,b)\).

Input/Output: The input consists of the following:

• First line: an integer \(n\) (number of stations).
• Then for each of the 3 groups, there are \(n-1\) lines. Each line contains three integers \(u\), \(v\), and \(w\), representing an edge between stations \(u\) and \(v\) with user count \(w\).

The output is a single integer, the maximum total user count over all possible choices of \(a, b\). You may assume the input graphs are trees (connected and acyclic).

inputFormat

The first line contains an integer \(n\) (number of stations). The following 3\times(n-1) lines describe the three groups of teleportation channels. For each group, there are n-1 lines. Each line contains three space-separated integers \(u\), \(v\), and \(w\) indicating that there is a channel between stations \(u\) and \(v\) with usage count \(w\).

outputFormat

Output a single integer, the maximum sum of channel user counts over the three days, i.e. the maximum value of \(d_1(a,b)+d_2(a,b)+d_3(a,b)\) among all pairs of stations \(a\) and \(b\).

sample

3
1 2 10
2 3 20
1 2 5
2 3 5
1 2 7
2 3 8

55