#include<bits/stdc++.h>
using namespace std;
queue<int> q;
short xy[10]={1,0},yx[10]={0,1};
int x,y,z,n,m=1,l=1,r=1,a[10][10],s[1000],h=0;
int bfs(){
	for(int i=1;i<=81;i++){
		if(l==0&&m==0&&r==0){
			break;
		}
		cin >> l >> r >> m;
		a[l][r]=m;
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//			cout << a[i][j] << " ";
//		}
//		cout << endl;
//	}
	q.push(1);
	q.push(1);
	q.push(a[1][1]);
	while(!q.empty()){
		x=q.front();q.pop();
		y=q.front();q.pop();
		z=q.front();q.pop();
		if(x==n&&y==n){
			h++;
			s[h]=z;
		//	cout << z << endl;
			continue;
		}
		for(int i=0;i<2;i++){
			q.push(x+xy[i]);
			q.push(y+yx[i]);
			q.push(z+a[x+xy[i]][y+yx[i]]);
		}
	}
}
int main(){
	memset(a,0,sizeof(a));
	cin >> n;
	bfs();
	sort(s+1,s+1+h);
	cout << s[h-1]+s[h];
	return 0;
}