#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define maxn 1000
#define maxe 12
using namespace std;
int asd[maxe][maxe],n;
int prevv[maxn],prevu[maxn];
struct edge{
	int to,cap,cost,rev;
};
vector<edge>G[maxn];
void addedge(int from,int to,int cap,int cost){
	G[from].push_back((edge){to,cap,cost,G[to].size()});
	G[to].push_back((edge){from,0,-cost,G[from].size()-1});

}
void SPFA(int s){
	queue<int>que;
	que.push(s);
	bool inq[maxn];
	long long dist[maxn];
	memset(prevu,0,sizeof(prevu));	
	memset(prevv,0,sizeof(prevv));
    memset(inq,0,sizeof(inq));
	memset(dist,-1,sizeof(dist));
	dist[s]=0;
	while(!que.empty()){
		int k=que.front();
		que.pop();
		inq[k]=0;
		for(int i=0;i<G[k].size();i++){
			edge &e=G[k][i];
			if((dist[e.to]==-1||dist[e.to]<dist[k]+e.cost)&&e.cap>0){
				dist[e.to]=dist[k]+ e.cost;
				prevv[e.to]=k;
				prevu[e.to]=i;
				if(!inq[e.to]){
					que.push(e.to);
					inq[e.to]=1;
				}
			}
		}
	}
}
void get_input(){
	cin>>n;
	int a,b,c;
	while(cin>>a>>b>>c){
		if(a==0)
		break;
		asd[a][b]=c;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int t=(i-1)*n+j+1,k=i*n+j+1,f=(i-1)*n+j+2;
			addedge(t*2,t*2+1,1,asd[i][j]);
			if(i!=n)
			addedge(t*2+1,k*2,1,0);
			if(j!=n)
			addedge(t*2+1,f*2,1,0);
		}
	}
	addedge(4,5,1,0);
	addedge(((n-1)*n+n+1)*2,((n-1)*n+n+1)*2+1,1,0);
}
int work(){
	SPFA(4);
	int t=((n-1)*n+n+1)*2+1;
	int ans=0;
	while(t!=4){
		int v=prevv[t],u=prevu[t];
		edge &e=G[v][u];
		e.cap-=1;
		G[e.to][e.rev].cap+=1;
		ans+=e.cost;
		t=prevv[t];
	}
	return ans;
}
int main(){
	freopen("fgqs.in","r",stdin);
	freopen("fgqs.out","w",stdout);
	get_input();
	cout<<work()+work();
}