/*
先求各点到1的最短路
然后从个最短路中找到最大值
原型:int atoi(const char *nptr);
函数说明:参数nptr字符串，如果第一个非空格字符不存在或者不是数字也不是正负号则返回0，
否则开始做类型转换，之后检测到非数字(包括结束符 \0) 字符时停止转换，返回整型数。
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int map[110][110],vis[110],dist[110],n;
char s[1000];
int zhao()
{
int i,xia=-1;
for(i=1;i<=n;i++)
if(vis[i]==0&&(xia==-1||dist[i]<dist[xia]))
xia=i;
return xia;
}
int dijkstra()
{
int max=0,i,j,xia;
memset(vis,0,sizeof(vis));
vis[1]=1;
for(i=1;i<=n;i++)
dist[i]=map[1][i];
for(i=2;i<=n;i++)
{
xia=zhao();
vis[xia]=1;
for(j=1;j<=n;j++)
if(vis[j]==0&&dist[j]>dist[xia]+map[xia][j])
dist[j]=dist[xia]+map[xia][j];
}
for(i=2;i<=n;i++)
if(dist[i]>max)
max=dist[i];
return max;
}
int main()
{
int i,j,k;
scanf("%d",&n);
getchar();
for(i=2;i<=n;i++)
{
gets(s);
j=1;
k=0;
while(s[k])
{
if(s[k]=='x')
{
map[i][j++]=999999999;
k=k+2;
continue;
}
map[i][j++]=atoi(s+k);
while(s[k]>='0'&&s[k]<='9')
k++;
while(s[k]==' ')
k++;
}
}
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
if(i==j)
map[i][i]=0;
else map[i][j]=map[j][i];
}
printf("%d\n",dijkstra());
return 0;
}