// Arup Guha
// 8/18/2016
// Solution to 2014 World Finals Problem G: Metal Processing Plant

// Note: I am not 100% sure this works, but it passes all the WF data.
//       I had to do something hokey with my status function to
//       get this solution to work, but I think I have a rationale for
//       what I did.

import java.util.*;

public class g {

	final public static int IMPOSSIBLE = -1;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int n = stdin.nextInt();

		Edge[] all = new Edge[n*(n-1)/2];

		// Read in the data.
		int cnt = 0;
		for (int i=0; i<n; i++)
			for (int j=i+1; j<n; j++)
				all[cnt++] = new Edge(i,j,stdin.nextInt());

		// Sort edges big to small and solve it.
		Arrays.sort(all);
		System.out.println(solve(all, n));
	}

	public static int solve(Edge[] all, int n) {

		// Get rid of easy cases.
		if (n < 3) return 0;

		int res = all[0].weight;

		// Try each possible break point - first represents the first time
		// we put both items on an edge in the same group.
		for (int first=1; first<all.length; first++) {
			int cur = bestAnsK(all, n, first);
			if (cur == -1) break;
			res = Math.min(res, cur);
		}
		return res;
	}

	// I have to put 2 first since that status takes precedence over 1.
	// 2 = on opposite of big side, 1 = on same side as big side
	// 3 means not connected to the big side or its opposite.
	public static int status(dj set, int big, int item) {
		if (set.find(2*big) == set.find(2*item+1)) return 2;
		if (set.find(2*big) == set.find(2*item)) return 1;
		return 3;
	}

	// Uses a greedy approach to find the best answer given that we split the first k edges apart and put edge k+1 in the same set.
	public static int bestAnsK(Edge[] all, int n, int k) {

		dj set = new dj(2*n);

		// Force apart first k edges.
		for (int i=0; i<k; i++) {
			int v1 = all[i].source;
			int v2 = all[i].dest;
			boolean resA = set.union(2*v1, 2*v2+1);
			boolean resB = set.union(2*v1+1, 2*v2);
			if (set.find(2*v1) == set.find(2*v2)) return -1;
		}

		// In this case, the edges we want on the same side are on different sides, so this case is impossible.
		if (set.find(2*all[k].source) == set.find(2*all[k].dest+1)) return 2000000000;

		// Vertex on the same side that contains the largest same side edge.
		int big = all[k].source;

		// Put these two on the same side.
		set.union(2*all[k].source, 2*all[k].dest);
		set.union(2*all[k].source+1, 2*all[k].dest+1);

		// This is our cost.
		int res = all[k].weight;
		int curE = k+1;

		// Now, split apart future edges for as long as we can.
		while (curE < all.length) {

			// Figure out where in our current set up v1 and v2 are.
			int v1 = all[curE].source;
			int v2 = all[curE].dest;
			int status1 = status(set, big, v1);
			int status2 = status(set, big, v2);

			// Oops, this edge is on the opposite side, so we're done.
			if (status1 == 2 && status2 == 2) {
				res += all[curE].weight;
				break;
			}

			// Greedily put these two on the same side as the big side, because we can and we want to minimize vertices
			// on the other side when we have a choice.
			else if (status1==3 && status2==3) {
				set.union(2*v1, 2*v2);
				set.union(2*v1+1, 2*v2+1);
				set.union(2*v1, 2*big);
				set.union(2*v1+1, 2*big+1);
			}

			// We definitely want to merge the unassigned vertex into the side with the big edge.
			else if (status1+status2 == 4) {
				set.union(2*v1, 2*v2);
				set.union(2*v1+1, 2*v2+1);
			}

			// We definitely want to put the unassigned vertex into the side with the big edge, opposite the other vertex.
			else if (status1+status2 == 5) {
				set.union(2*v1, 2*v2+1);
				set.union(2*v1+1, 2*v2);
			}

			curE++;
		}

		// Ta da!
		return res;
	}
}

class Edge implements Comparable<Edge> {

	public int source;
	public int dest;
	public int weight;

	public Edge(int from, int to, int w) {
		source = from;
		dest = to;
		weight = w;
	}

	public int compareTo(Edge other) {
		return other.weight - this.weight;
	}
}

// Basic Disjoint Set class with path compression.
class dj {

	private int[] parent;

	public dj(int n) {
		parent = new int[n];
		for (int i=0; i<n; i++)
			parent[i] = i;
	}

	public int find(int node) {
		if (parent[node] == node) return node;
		int retval = find(parent[node]);
		parent[node] = retval;
		return retval;
	}

	public boolean union(int a, int b) {
		int pa = find(a);
		int pb = find(b);
		if (pa == pb) return false;
		parent[pb] = pa;
		return true;
	}
}