#include <stdio.h>
#include <string.h>
#define len 10050
typedef struct node
{
	int s;
	int e;
	int d;
}Node;
Node point[len];
int n,countedge;
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;
}
void addedge(int s,int e,int d)
{
	point[countedge].s=s;
	point[countedge].e=e;
	point[countedge++].d=d;
}
void bellman()
{
	int dist[len],i,j,sum;
	for(i=1;i<=n;i++)
		dist[i]=10000000;
	dist[1]=0;
	for(i=1;i<n;i++)
		for(j=0;j<countedge;j++)
			if(dist[point[j].e]>dist[point[j].s]+point[j].d)
				dist[point[j].e]=dist[point[j].s]+point[j].d;
			sum=0;
      for(i=2;i<=n;i++)
		  if(dist[i]>sum)
			  sum=dist[i];
		  printf("%d\n",sum);
}
int main()
{
	int i,j,t;
	char str[100];
	while(scanf("%d",&n)!=EOF)
	{
		countedge=0;
		for(i=1;i<=n;i++)
			for(j=1;j<i;j++)
			{
				scanf("%s",str);
				t=cal(str);
				if(!t)
				{
					addedge(i,j,10000000);
					addedge(j,i,10000000);
				}
				else
				{
					addedge(i,j,t);
					addedge(j,i,t);
				}
			}
			bellman();
	}
	return 1;
}