#include<bits/stdc++.h>
#define pfin (i-1)*n+j
#define pfout (i-1)*n+j+n*n
using namespace std;
const int N = 5010, M = 100010, INF = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
int nums[10][10];

void add(int a, int b, int c, int d)
{
	e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
	e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}

bool spfa()
{
	int hh = 0, tt = 1;
	memset(d, 0x3f, sizeof d);
	memset(incf, 0, sizeof incf);
	q[0] = S, d[S] = 0, incf[S] = INF;
	while(hh != tt)
	{
		int t = q[hh++];
		if(hh == N) hh = 0;
		st[t] = false;

		for(int i = h[t]; ~i; i = ne[i])
		{
			int ver = e[i];
			if(f[i] && d[ver] > d[t] + w[i])
			{
				d[ver] = d[t] + w[i];
				pre[ver] = i;
				incf[ver] = min(f[i], incf[t]);
				if(!st[ver])
				{
					q[tt++] = ver;
					if(tt == N) tt = 0;
					st[ver] = true;
				}
			}
		}
	}

	return incf[T] > 0;
}

void EK(int &flow, int &cost)
{
	flow = cost = 0;
	while(spfa())
	{
		int t = incf[T];
		flow += t, cost += t * d[T];
		for(int i = T; i != S; i = e[pre[i] ^ 1])
		{
			f[pre[i]] -= t;
			f[pre[i] ^ 1] += t;
		}
	}
}

int main()
{
	scanf("%d", &n);
	memset(h, -1, sizeof h);
	int a, b, c;
	while(scanf("%d%d%d", &a, &b, &c))
	{
		if((a == 0) && (b == 0) && (c == 0))break;
		nums[a][b] = c;
	}
	S = 0, T = 2 * n * n + 1;
	add(S, 1, 2, 0);
	add(2 * n * n, T, 2, 0);
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			add(pfin, pfout, 1, -nums[i][j]);
			add(pfin, pfout, 1, 0);
			if(j != n)add(pfout, pfin + 1, 2, 0);
			if(i != n)add(pfout, pfin + n, 2, 0);
		}
	}
	int flow, cost;
	EK(flow, cost);
	printf("%d\n", -cost);
	return 0;
}