#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxx = 1e3 + 10;

int mp[maxx][maxx];

int main()
{
    int n;
    char ss[15];
    while(cin>>n)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=i; j++)
            {
                if (i == j)
                {
                    mp[i][j] = 0;
                    continue;
                }
                scanf("%s",ss);
                if (ss[0] == 'x')
                    mp[i][j] = mp[j][i] = INF;
                else
                {
                    int l = strlen(ss);
                    int sum = 0;
                    for(int i=0; i<l; i++)
                    {
                        int c = ss[i] - '0';
                        sum =sum * 10 + c;
                    }
                    mp[i][j] = mp[j][i] = sum;
                }
            }
        }
        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                {
                    if (mp[i][j] > mp[i][k]+mp[k][j])
                        mp[i][j] = mp[i][k]+mp[k][j];
                }
//        for(int i=1; i<=n; i++)
//        {
//            puts("");
//            for(int j=1; j<=n; j++)
//            {
//                printf("%d\t",mp[i][j]);
//            }
//        }
        int ans = 0;
        for(int i=1; i<=n; i++)
        {
            ans =max(ans,mp[1][i]);
        }
        cout<<ans<<endl;




    }

    return 0;
}