[kug]

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;


class polaczenie
{public:
    int i,j;
    int koszt;
    bool operator < (const polaczenie& other ) const {return koszt<other.koszt;}
    polaczenie (int ii,int jj,int k):i(ii),j(jj),koszt(k){}
};


int main()
{

    int n;
    cin.sync_with_stdio(false);

    cin>>n;

    //generator zośliwego przypadku
    /*cout<<n<<endl;
    for (int i=1;i<=n;i++)
    {
        //if (i<n) cout<<"1 ";
        for(int j=i;j<=n-1;j++)
        {
            cout<<j-i+1<<" ";
        }
        cout<<2*n<<" "<<endl;
    }
    return 0;*/


    vector <polaczenie> polaczenia;
    polaczenia.reserve((n+2)*(n+2)/2);

    for (int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
        {
            int c;
            cin>>c;
        //    C[i][j]=c;
            polaczenia.emplace_back(i,j,c);
        }


    sort(polaczenia.begin(),polaczenia.end());

    vector<int> konce(n+1,0);  // koniec[i]=j oznacza belkę i-j.

    int wymiar=0;
    int index=0;
    int64_t koszt=0;
    while (wymiar<n)
    {
        polaczenie belka = polaczenia[index];
        index++;

        while ( konce[belka.i]!=0 )
        {
            if (konce[belka.i]==belka.j)
            {
             //   cout<<"jest"<<endl;
                belka.i=0;
                break;
            }

            int M,m;
            if (konce[belka.i]>belka.j)
            {
                M=konce[belka.i];
                m=belka.j;
            }else
            {
                m=konce[belka.i];
                M=belka.j;
            }

            //heurystyka walczaca z O(n^3)
            //chcemy, aby belka bazowa zajmowałą z grubsza
            //polowę miejsca miedzy swoim początkiem a końcem.
            if ( abs(M-(belka.i+n/2))<abs(m-(belka.i+n/2) ) )
                 konce[belka.i]=M;
            else
                 konce[belka.i]=m;
            //nie wiemy jeszcze, czy belka wejdzie do bazy, ale
            //jeśli nie wejdzie, tzn była liniiowo zależna od bazy
            // - mamy prawo ją odjąć.


            belka.i=m+1;
            belka.j = M;


        }
        if (belka.i!=0)
        {
            konce[belka.i]=belka.j;
            wymiar++;
            koszt+=belka.koszt;
        }

    }


    cout<<koszt<<endl;


    return 0;
}