#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int size = 10010;
#define maxint 999999
int total;
struct Edge
{
       int u;
       int v;
       int weight;
};
class poj1502
{
      private:
              Edge edge[size];
              int dist[size];
      public:
             int nodenum;
             int edgenum;
             void addEdge(int,int,int);
             void input();
             void relax(int,int,int);
             void bellman();  
};
int translate(char str[])
{
    int sum=0,index,len;
    if(str[0]=='x')
    return -1;
    else
    {
        len=strlen(str);
        for(index=0;index<len;index++)
        sum=sum*10+(str[index]-'0');
    }
    return sum;    
}
void poj1502::addEdge(int u,int v,int weight)
{
     edge[total].u=u;
     edge[total].v=v;
     edge[total].weight=weight;
     total++;
}
void poj1502::input()
{
     edgenum=(nodenum-1)*(nodenum);
     char w[20];
     int weight,k=1;
     total=1;
     for(int i=2;i<=nodenum;i++)
     {
             for(int j=1;j<i;j++)
             {
                     scanf("%s",w);
                     weight=translate(w);
                     if(weight==-1)
                     {
                                   addEdge(i,j,maxint);
                                   addEdge(j,i,maxint);
                     }
                     else
                     {
                         addEdge(i,j,weight);
                         addEdge(j,i,weight);
                     }
             }
     }
}
void poj1502::relax(int s,int e,int w)
{
     if(dist[e]>dist[s]+w)
     dist[e]=dist[s]+w;
}
void poj1502::bellman()
{
     for(int k=1;k<=nodenum;k++)
     dist[k]=maxint;
     dist[1]=0;
     for(int i=1;i<nodenum;i++)
     {
             for(int j=1;j<=edgenum;j++)
             {
                     relax(edge[j].u,edge[j].v,edge[j].weight);
             }
     }
     int min=0;
     for(int k=2;k<=nodenum;k++)
     if(dist[k]>min)
     min=dist[k];
     cout<<min<<endl;
}
int main()
{
    poj1502 t;
    while(scanf("%d",&t.nodenum)!=EOF)
    {
                                      t.input();
                                      t.bellman();
    }                                 
    return 1;
}