#include <iostream>

using namespace std;


int findMinElement(int **a, int n, int j, bool flag) // true - поиск минимума в строке, false - в столбце
{
    int min = 0;
    for (int i = 0; i < n; i++)
        if ((flag && a[j][min] > a[j][i]) || (!flag && a[min][j] > a[i][j]))
            min = i;

    return min;
}

int calcRating(int **arr, int n, int a, int b)
{
    int min_str = INT_MAX, min_col = INT_MAX;
    for (int i = 0; i < n; i++)
    {
        if (arr[a][i] < min_str && i != b)
            min_str = arr[a][i];
        if (arr[i][b] < min_col && i != a)
            min_col = arr[i][b];
    }

    if (min_str == INT_MAX)
        min_str = 0;
    if (min_col == INT_MAX)
        min_col = 0;
    return min_str + min_col;
}




int main()
{
    int n, result;
    int **g, **temp, **solve, *path;
    cin >> n;

    path = new int[n];
    g = new int*[n];
    temp = new int*[n];
    solve = new int*[n];
    for (int i = 0; i < n; i++)
    {
        g[i] = new int[n];
        temp[i] = new int[n];
        solve[i] = new int[n];
    }


    int a;
    for (int i = 0; i < n; i++)
    {
        path[i] = -1;
        for (int j = 0; j < n; j++)
        {

            if (i != j)
            {
                cout << i + 1 << " " << j + 1 << ": ";
                cin >> a;
                g[i][j] = a;
            }
            else
                g[i][j] = INT_MAX;
            solve[i][j] = g[i][j];
        }
    }

    int count = 0;
    while (count < n - 1)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
                temp[i][j] = solve[i][j];
        }


        int min;

        //минимум по строке
        for (int i = 0; i < n; i++)
        {
            result = findMinElement(temp, n, i, true);
            min = temp[i][result];
            for (int j = 0; j < n; j++)
                if (temp[i][j] != INT_MAX)
                    temp[i][j] -= min;
        }

        //минимум по столбцу
        for (int i = 0; i < n; i++)
        {
            result = findMinElement(temp, n, i, false);
            min = temp[result][i];
            for (int j = 0; j < n; j++)
                if (temp[j][i] != INT_MAX)
                    temp[j][i] -= min;
        }


        //вычисление оценок для нулевых клеток (находим максимальную оценку)
        int i_maxIndex, j_maxIndex, maxValue = -1;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (temp[i][j] == 0)
                {
                    result = calcRating(temp, n, i, j);
                    if (result > maxValue)
                    {
                        maxValue = result;
                        i_maxIndex = i;
                        j_maxIndex = j;
                    }
                }
            }
        }

        // записываем путь
        path[i_maxIndex] = j_maxIndex;

        //удалем строку и столбец
        for (int i = 0; i < n; i++)
        {
            solve[i][j_maxIndex] = INT_MAX;
            solve[i_maxIndex][i] = INT_MAX;
        }

        //удаляем обратный путь
        solve[j_maxIndex][i_maxIndex] = INT_MAX;



        count++;
    }

    //в конце всегда остается только 1 дорога - замыкающая
    int start, end;
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (solve[i][j] != INT_MAX)
            {
                start = j;
                end = i;
                ans += solve[i][j];
            }


    //востанавливаем путь
    for (int i = start; path[i] != -1; i = path[i])
    {
        cout << i + 1 << "->";
        ans += g[i][path[i]];
    }
    cout << end + 1  << "->" << start + 1 << endl;
    cout << ans << endl;

    return 0;
}


/*
4
5
11
9
10
8
7
7
14
8
12
6
15

*/


/*

4
5
1
4
3
2
1
7
6
4
2
5
3



*/