#include<bits/stdc++.h>
using namespace std;
//0-O -1번 거점, 1-A -2번 거점, 2-B -3번 거점, 3-C -4번 거점, 4-D -5번 거점, 5-E -6번 거점, 6-F -7번 거점, 7-G -8번 거점
int path[8][8] = {};
bool visited[8] = {};
vector<int> v[8] = {};
void set_distance() {//단위 처리, 소수점 처리하기 귀찮으니 *10으로 처리해줌
    path[1][0] = path[0][1] = 42;
    path[2][0] = path[0][2] = 38;
    path[3][0] = path[0][3] = 37;
    path[4][0] = path[0][4] = 16;
    path[5][0] = path[0][5] = 25;
    path[6][0] = path[0][6] = 36;
    path[7][0] = path[0][7] = 44;

    path[1][2] = path[2][1] = 42;
    path[1][3] = path[3][1] = 50;
    path[1][4] = path[4][1] = 47;
    path[1][5] = path[5][1] = 57;
    path[1][6] = path[6][1] = 53;
    path[1][7] = path[7][1] = 34;

    path[2][3] = path[3][2] = 45;
    path[2][4] = path[4][2] = 48;
    path[2][5] = path[5][2] = 55;
    path[2][6] = path[6][2] = 70;
    path[2][7] = path[7][2] = 67;

    path[3][4] = path[4][3] = 32;
    path[3][5] = path[5][3] = 53;
    path[3][6] = path[6][3] = 66;
    path[3][7] = path[7][3] = 70;

    path[4][5] = path[5][4] = 23;
    path[4][6] = path[6][4] = 45;
    path[4][7] = path[7][4] = 59;

    path[5][6] = path[6][5] = 29;
    path[5][7] = path[7][5] = 45;

    path[6][7] = path[7][6] = 25;
}
vector<int> tem_path[7] = {};
int tem = 1e9;
void find_line(int idx,int cnt,int sum,int goal) {
    //cout << idx << " " << "* ";
    if (goal == v[cnt].size()) {
        if (visited[0]) {
            //cout << tem << " " << sum << "**\n";
            if (tem > sum) {
                tem = sum;
                while (!tem_path[cnt].empty()) tem_path[cnt].pop_back();
                for (int i : v[cnt]) tem_path[cnt].push_back(i);
            }
        }
        return;
    }
    for (int i = 0; i <= 7; i++) {
        if (!visited[i]) {
            v[cnt].push_back(i);
            visited[i] = 1;
            find_line(i, cnt, sum + path[idx][i], goal);
            v[cnt].pop_back();
            visited[i] = 0;
        }
    }
}
void reset(int g) {
        while (!v[g].empty()) v[g].pop_back();
        while (!tem_path[g].empty()) tem_path[g].pop_back();
        tem = 1e9;
        for (int i = 0; i <= 7; i++) visited[i] = 0;
}
int main() {
    set_distance();
    for (int i = 1; i <= 1; i++) {//버스 대수
        for (int g = 1; g <= 1; g++) {//버스 라인 배정
            int final = 1e9;
            vector<int> final_path[8] = {};
            for (int z = 1; z <= 7; z++) {//버스 시작 라인
                reset(g);//라인 초기화

                if (!visited[z]) {
                    v[g].push_back(z);
                    visited[z] = 1;
                    find_line(z, g, 0, 7 / i + 1);//현재 위치, 버스 라인 인덱스, 거리 총합, 목표
                    visited[z] = 0;
                    v[g].pop_back();
                }
                //if (final > tem) {
                //  final = tem;
                //  for (int q : tem_path[g]) final_path[g].push_back(q);
                //}

                cout <<z<<" "<< tem << "\n";
                for (int q : tem_path[g]) cout << q << " ";
                cout << "\n";
            }
            //cout << "cost : " << final << "\npath -> ";
            //for (int z : final_path[g]) cout << z << " ";
            //cout << "\n";
        }
    }
}