#include <stdio.h> 
#include <string.h> 
int d[1002],visit[1002],n; 
int edges[1005][1005]; 
int queue[1000001]; 
#define MAX 999999999 
#define N 1001 
void SPFA(int s) 
{ 
    int i; 
    int front = 0, rear = 1,sum;  
	memset(visit,0,sizeof(visit));
    memset(queue,0,sizeof(queue)); 
    for(i=1;i<=n;i++) 
     d[i] = MAX; 
    queue[front] = s; 
    visit[s] = true; 
    d[s] = 0; 
    while(front<rear) 
    { 
        int u=queue[front]; 
        visit[u]=0; 
        for(int i=1; i<=n; i++) 
        { 
            if (d[i]>d[u]+ edges[u][i]) 
            { 
                d[i]=d[u]+edges[u][i];
                if( !visit[i] ) 
                { 
                    visit[i]=1; 
                    queue[rear++]=i; 
                } 
            } 
        } 
        front++; 
    } 
	sum=0;
	for(i=2;i<=n;i++)
		if(d[i]>sum)
			sum=d[i];
		printf("%d\n",sum);
   
} 
int cal(char str[])
{
	int i,res=0;
	if(str[0]=='x')
		return 0;
	for(i=0;str[i];i++)
		res=res*10+(str[i]-'0');
	return res;
}
int main() 
{ 
    int i,j,t; 
	char str[100];
    while(scanf("%d",&n)!=EOF) 
    { 
        for(i=1;i<=n;i++)
		{ 
            for(j=1;j<i;j++) 
            { 
                edges[i][j]=MAX; 
                edges[j][i]=MAX; 
            } 
        } 
        for(i=1;i<=n;i++) 
        { 
			for(j=1;j<i;j++)
            {
				scanf("%s",str); 
				t=cal(str);
				if(!t)
				{
					edges[i][j]=MAX;
					edges[j][i]=MAX;
				}
				else
				{
					edges[i][j]=t;
					edges[j][i]=t;
				}
			}
        } 
        SPFA(1); 
    } 
    return 0; 
}