#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <map>
#include <tuple>
#include <iostream>
#include <deque>
#include <array>
#include <set>
#include <functional>
#include <memory>
#include <stack>
#include <numeric>

class UnionFind {
	std::vector<int> _parent;
public:
	UnionFind(const int size) : _parent(size, -1) {};
	int find(const int a) {
		if (_parent[a] < 0) return a;
		else return _parent[a] = find(_parent[a]);
	}
	bool is_same(const int a, const int b) {
		return find(a) == find(b);
	}
	void merge(const int a, const int b) {
		const auto ar = find(a);
		const auto br = find(b);
		if (ar != br) {
			if (_parent[ar] < _parent[br]) {
				_parent[ar] += _parent[br];
				_parent[br] = ar;
			}
			else {
				_parent[br] += _parent[ar];
				_parent[ar] = br;
			}
		}
	}
	void clear() {
		std::fill(_parent.begin(), _parent.end(), -1);
	}
};
struct Edge {
	int from, to;
	Edge(const int f, const int t) : from{ std::min(f, t) }, to{ std::max(f, t) }{}
	bool operator<(const Edge& other) const { return (from == other.from) ? to < other.to : from < other.from; }
};
int main() {
	std::cin.tie(0); std::ios::sync_with_stdio(false);
	while (true) {
		int n; std::cin >> n;
		if (n == 0) break;
		std::vector<std::vector<int>> weights(n, std::vector<int>(n, 0));
		for (auto i = 0; i < n - 1; ++i) {
			int e;
			for (auto j = i + 1; j < n; ++j) {
				std::cin >> e;
				weights[i][j] = weights[j][i] = e;
			}
		}
		std::vector<bool> is_flip(n, false);
		UnionFind union_find(n);
		auto temp_cost = 0;
		auto count = 0;
		is_flip[1] = weights[0][1] < 0;
		for (auto i = 2; i < n; ++i) {
			is_flip[i] = weights[0][i] > 0;
		}
		std::set<Edge> set; set.emplace(0, 1);
		for (auto f = 1; f < n; ++f) for (auto t = f + 1; t < n; ++t) if ((is_flip[f] == is_flip[t]) == weights[f][t] > 0) { set.emplace(f, t); }
		std::vector<std::vector<bool>> connection(n, std::vector<bool>(n, false));
		int min = INT_MAX;
		for (auto a = 1; a < n; ++a) {
			if (a != 1) {
				for (auto i = 0; i < n; ++i) {
					if (i != a && i != a - 1) {
						if ((weights[0][a] < 0 == weights[0][i] > 0) == (weights[a][i] > 0)) {
							set.emplace(a, i);
						}
						else {
							set.erase(Edge{ std::min(a, i), std::max(a, i) });
						}
						if ((weights[0][a - 1] > 0 == weights[0][i] > 0) == (weights[a - 1][i] > 0)) {
							set.emplace(a - 1, i);
						}
						else {
							set.erase(Edge{ std::min(a - 1, i), std::max(a - 1, i) });
						}
					}
				}
			}
			if (set.size() == n - 1) {
				union_find.clear();
				temp_cost = 0;
				for (const auto& e : set) {
					if (union_find.is_same(e.from, e.to)) {
						temp_cost = INT_MAX;
						break;
					}
					else {
						union_find.merge(e.from, e.to);
						temp_cost += std::abs(weights[e.from][e.to]);
					}
				}
				if (min > temp_cost) min = temp_cost;
			}
			is_flip[a] = weights[0][a] < 0;
			for (auto b = 1; b < n; ++b) if (!(a == b || connection[a][b] || ((is_flip[a] == weights[b][0] < 0) == weights[b][a] > 0))) {
				if (b == n) continue;
				is_flip[b] = weights[0][b] < 0;
				temp_cost = 0;
				count = 0;
				for (auto i = 1; i < n; ++i) if (i != a && i != b) {
					is_flip[i] =
						(((weights[i][0] > 0) ? 1 : 0) +
						((is_flip[a] == weights[i][a] < 0) ? 1 : 0) +
							((is_flip[b] == weights[i][b] < 0) ? 1 : 0)) > 1;
				}
				union_find.clear();
				auto calculated = false;
				for (auto t = 1; t < n && !calculated; ++t) {
					if ((is_flip[t] == weights[0][t] < 0)) {
						union_find.merge(0, t);
						temp_cost += std::abs(weights[0][t]);
						++count;
						if (t != a)calculated = connection[a][t] || connection[b][t];
					}
				}
				if (!calculated) {
					for (auto f = 1; f < n && count < n; ++f) for (auto t = f + 1; t < n && count < n; ++t) {
						if ((is_flip[f] == is_flip[t]) == weights[f][t] > 0) {
							if (union_find.is_same(f, t)) {
								temp_cost = INT_MAX; count = n; break;
							}
							else {
								union_find.merge(f, t);
								temp_cost += std::abs(weights[f][t]);
								++count;
							}
						}
					}
					if (count == n - 1 && temp_cost != INT_MAX) {
						if (min > temp_cost) min = temp_cost;
					}
				}
				connection[a][b] = connection[b][a] = true;
				for (auto t = 1; t < n; ++t) {
					if (t != a && t != b && (is_flip[t] == weights[0][t] < 0)) {
						connection[a][t] = connection[t][a] = connection[b][t] = connection[t][b] = true;
					}
				}
			}
		}
		std::cout << ((min == INT_MAX) ? -1 : min) << '\n';
	}
}


Measured memory_bytes: 5220