#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    int n,koszt,krok,z;
    int tab[100][100], poz[100][2];

    ifstream dane;
    dane.open("dane.txt");

    dane >> n;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            dane >> tab[i][j];
        }
    }

dane.close();

/* wyswietlanie danych
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cout << tab[i][j];
        }
        cout << endl;
    }
*/


koszt=0;
z=n-1;
int y=0;
krok=0;
koszt += tab[z][y];
poz[krok][0]=z;
poz[krok][1]=y;
cout << z << " " << y << endl;
krok++;


for(int i=0;i<2*n-2;i++)
{
    if( (tab[z-1][y]<= tab[z][y+1] && z>0) || y==n-1)
    {
        z--;
        koszt += tab[z][y];
        cout << z << " " << y << endl;
        poz[krok][0]=z;
        poz[krok][1]=y;
        krok++;

    }
    else
    {
        y++;
        koszt += tab[z][y];
        cout << z << " " << y << endl;
        poz[krok][0]=z;
        poz[krok][1]=y;
        krok++;

    }

}

ofstream wynik;
wynik.open("wynik.txt");


cout << "Koszt: " << koszt;
wynik << "Koszt: " << koszt << endl;

for(int i=0;i<=2*n-2;i++)
{
    wynik << poz[i][0] << " " << poz[i][1] << endl;
}

wynik.close();
    return 0;
}