#include <stdio.h>
#include <string.h>
#define len 1010
#define INF 10000000
int road[len][len],dist[len],s[len];
int n;
int cal(char str[])
{
	int res=0,i;
	if(str[0]=='x')
		return 0;
	else
	{
		for(i=0;str[i];i++)
		res=res*10+(str[i]-'0');
	}
	return res;
}	
void distra()
{
  int i,j,mindistance,rec,sum;
  for(i=1;i<=n;i++)
  dist[i]=road[1][i];
  memset(s,0,sizeof(s));
  s[1]=1;
  for(i=1;i<n;i++)
  {
	  mindistance=INF;
	  rec=-1;
	  for(j=1;j<=n;j++)
		  if(!s[j]&&dist[j]<mindistance)
		  {
			  mindistance=dist[j];
			  rec=j;
		  }
		  s[rec]=1;
		  for(j=1;j<=n;j++)
			  if(!s[j]&&(dist[rec]+road[rec][j])<dist[j])
				  dist[j]=dist[rec]+road[rec][j];
  }
  sum=0;
  for(i=2;i<=n;i++)
	if(dist[i]>sum)
		sum=dist[i];
  printf("%d\n",sum);
}
int main()
{
	int s,e,i,j,temp;
	char str[20];
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
				road[i][j]=INF;
			road[i][i]=0;
		}
		for(i=1;i<=n;i++)
		{
			for(j=1;j<i;j++)
			{
				scanf("%s",str);
				temp=cal(str);
                if(temp==0)
				{
					road[i][j]=INF;
					road[j][i]=INF;
				}
				else
				{
					road[i][j]=temp;
					road[j][i]=road[i][j];
				}
			}
		}
	distra();
	}
	return 1;
}