You are given n blocks, each of them is of the form [color_1|value|color_2], where the block can also be flipped to get [color_2|value|color_1]. 

A sequence of blocks is called valid if the touching endpoints of neighboring blocks have the same color. For example, the sequence of three blocks A, B and C is valid if the left color of the B is the same as the right color of the A and the right color of the B is the same as the left color of C.

The value of the sequence is defined as the sum of the values of the blocks in this sequence.

Find the maximum possible value of the valid sequence that can be constructed from the subset of the given blocks. The blocks from the subset can be reordered and flipped if necessary. Each block can be used at most once in the sequence.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 100) — the number of given blocks.

Each of the following n lines describes corresponding block and consists of color_{1,i}, value_i and color_{2,i} (1 ≤ color_{1,i}, color_{2,i} ≤ 4, 1 ≤ value_i ≤ 100 000).

Output

Print exactly one integer — the maximum total value of the subset of blocks, which makes a valid sequence.

Examples

Input

6
2 1 4
1 2 4
3 4 4
2 8 3
3 16 3
1 32 2


Output

63

Input

7
1 100000 1
1 100000 2
1 100000 2
4 50000 3
3 50000 4
4 50000 4
3 50000 3


Output

300000

Input

4
1 1000 1
2 500 2
3 250 3
4 125 4


Output

1000

Note

In the first example, it is possible to form a valid sequence from all blocks.

One of the valid sequences is the following:

[4|2|1] [1|32|2] [2|8|3] [3|16|3] [3|4|4] [4|1|2]

The first block from the input ([2|1|4] → [4|1|2]) and second ([1|2|4] → [4|2|1]) are flipped.

In the second example, the optimal answers can be formed from the first three blocks as in the following (the second or the third block from the input is flipped):

[2|100000|1] [1|100000|1] [1|100000|2]

In the third example, it is not possible to form a valid sequence of two or more blocks, so the answer is a sequence consisting only of the first block since it is the block with the largest value.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Vadim Semenov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static final class TaskE {
        private static final int VERTICES = 4;
        private static final int EDGES = 6;
        private static final int[][] TYPE_BY_EDGE = new int[VERTICES][VERTICES];
        private static final TaskE.Edge[] EDGE_BY_TYPE = new TaskE.Edge[EDGES + VERTICES];

        static {
            prepare(TYPE_BY_EDGE, EDGE_BY_TYPE);
        }

        public void solve(int __, InputReader in, PrintWriter out) {
            int count = in.nextInt();
            List<TaskE.Edge>[] edges = new List[EDGES + VERTICES];
            int[] sum = new int[edges.length];
            Arrays.setAll(edges, i -> new ArrayList<>());
            for (int e = 0; e < count; ++e) {
                TaskE.Edge edge = TaskE.Edge.readEdge(in);
                int type = TYPE_BY_EDGE[edge.u][edge.v];
                edges[type].add(edge);
                sum[type] += edge.cost;
            }
            for (List<TaskE.Edge> list : edges) {
                list.sort(Comparator.reverseOrder());
            }
            boolean[][] state = new boolean[1 << 12][4];
            for (int i = 0; i < 4; ++i) {
                state[0][i] = true;
            }
            for (int mask = 0; mask < state.length; ++mask) {
                for (int color = 0; color < VERTICES; ++color) {
                    if (!state[mask][color]) continue;
                    for (int type = 0; type < EDGES; ++type) {
                        TaskE.Edge mock = EDGE_BY_TYPE[type];
                        if (!mock.contains(color)) continue;
                        int qty = (mask >> (2 * type)) & 0x3;
                        if (qty + 1 <= Math.min(3, edges[type].size())) {
                            int nextMask = mask ^ (qty << (2 * type)) ^ ((qty + 1) << (2 * type));
                            int nextColor = mock.next(color);
                            state[nextMask][nextColor] = true;
                        }
                    }
                }
            }
            int answer = 0;
            boolean[] visited = new boolean[VERTICES];
            for (int mask = 0; mask < state.length; ++mask) {
                for (int color = 0; color < VERTICES; ++color) {
                    if (!state[mask][color]) continue;
                    Arrays.fill(visited, false);
                    int current = sum[EDGES + color];
                    visited[color] = true;
                    for (int type = 0; type < EDGES; ++type) {
                        int qty = (mask >> (2 * type)) & 0x3;
                        if (qty == 0) continue;
                        current += sum[type];
                        if (qty % 2 != edges[type].size() % 2) {
                            current -= edges[type].get(edges[type].size() - 1).cost;
                        }
                        TaskE.Edge mock = EDGE_BY_TYPE[type];
                        for (int v : new int[]{mock.u, mock.v}) {
                            if (!visited[v]) {
                                visited[v] = true;
                                current += sum[6 + v];
                            }
                        }
                    }
                    answer = Math.max(answer, current);
                }
            }
            out.println(answer);
        }

        private static void prepare(int[][] typeByEdge, TaskE.Edge[] edgeByType) {
            int type = 0;
            for (int i = 0; i < VERTICES; ++i) {
                for (int j = 0; j < i; ++j) {
                    edgeByType[type] = new TaskE.Edge(i, j, 0);
                    typeByEdge[i][j] = typeByEdge[j][i] = type;
                    type++;
                }
            }
            for (int i = 0; i < VERTICES; ++i) {
                edgeByType[type] = new TaskE.Edge(i, i, 0);
                typeByEdge[i][i] = type;
                type++;
            }
        }

        private static class Edge implements Comparable<TaskE.Edge> {
            final int u;
            final int v;
            final int cost;

            static TaskE.Edge readEdge(InputReader in) {
                int u = in.nextInt() - 1;
                int cost = in.nextInt();
                int v = in.nextInt() - 1;
                return new TaskE.Edge(u, v, cost);
            }

            private Edge(int u, int v, int cost) {
                this.u = Math.max(u, v);
                this.v = Math.min(u, v);
                this.cost = cost;
            }

            boolean contains(int vertex) {
                return u == vertex || v == vertex;
            }

            int next(int vertex) {
                return vertex ^ u ^ v;
            }

            public int compareTo(TaskE.Edge o) {
                return Integer.compare(cost, o.cost);
            }

        }

    }

    static class InputReader {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(readLine());
            }
            return tokenizer.nextToken();
        }

        public String readLine() {
            String line;
            try {
                line = reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }

    }
}

