#include <iostream>
#include <cstring>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 105;
int e[maxn][maxn], dis[maxn], book[maxn];
int prim(int n);

int main()
{
    int n;
    while(cin>>n&&n)
    {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                cin>>e[i][j];

        cout<<prim(n)<<endl;
    }

    return 0;
}

int prim(int n)
{
    int wmin, v, cnt = 0, sum = 0;
    for(int i = 0; i < n; i++)
        dis[i] = e[0][i];

    memset(book, 0, sizeof(book));
    book[0] = 1;
    cnt++;

    while(cnt<n)
    {
        wmin = inf;
        for(int i = 0; i < n; i++)
        {
            if(book[i]==0&&dis[i]<wmin)
            {
                wmin = dis[i];
                v = i;
            }
        }
        if(wmin==inf)return -1;
        book[v] = 1;
        sum+=wmin;
        cnt++;

        for(int i = 0; i < n; i++)
            if(book[i]==0&&dis[i]>e[v][i])
                dis[i] = e[v][i];
    }

    return sum;
}