#include<bits/stdc++.h>
using namespace std;
//0-O-석산고, 1-A-서석고, 2-B-중남중(?), 3-C-광주여상(?), 4-D-봉선행정복지, 5-E-학동 중심사거리, 6-F-(이름 X), 7-G-광주역
int path[8][8] = {};
bool visited[8] = {};
vector<int> v[8] = {};
int idx = 0;
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<pair<pair<int, vector<int>>, string>> tem;
//first.first 거리 총합, first.second 노선, second 방문
vector<int> cur_path;
void find_path(int local_idx, int cost, int goal) {
    if (goal == 0) {
        string k = "00000000";
        for (auto i : cur_path) {
            k[i] = '1';
        }
        if (visited[0] == 1) tem.push_back({ { cost,cur_path },k });
        return;
    }
    for (int i = 0; i <= 7; i++) {
        if (visited[i] == 0) {
            cur_path.push_back(i);
            visited[i] = 1;
            find_path(i, cost + path[local_idx][i], goal - 1);
            visited[i] = 0;
            cur_path.pop_back();
        }
    }
}
int main() {
    set_distance();
    for (int g = 1; g <= 7; g++) {
        cur_path.push_back(g);
        visited[g] = 1;
        find_path(g, 0, 7 / 2 + 1);
        find_path(g, 0, 7 / 2 + 2);
        cur_path.pop_back();
        visited[g] = 0;
    }
    int final_cost = 1e9;
    vector<int> final_path[7] = {};
    std::sort(tem.begin(), tem.end());

    /*for (auto i : tem) {
        cout << i.first.first << " " << i.second << "\n";
        for (auto g : i.first.second) cout << g << " ";
        cout << "\n";
    }*/
    //cout << tem.size() << "\n";

    int ga, gb;

    for (int i = 0; i < tem.size(); i++) {
        int a = tem[i].first.first;
        int b = 1e9;
        if (a > final_cost) continue;
        string need = "11111111";
        for (auto g : tem[i].first.second) {
            //cout << g << " ";
            need[g] = '0';
        }
        int idx = -1;
        need[0] = '1';
        for (int g = i + 1; g < tem.size(); g++) {
            bool flag = 1;
            for (int z = 0; z < 8; z++) {
                if (need[z] == '1' && tem[g].second[z] == '0') flag = 0;
            }
            if (flag==1) {

                if (b > tem[g].first.first) {
                    b = tem[g].first.first;
                    idx = g;
                }
            }
        }
        if (idx == -1) continue;
        //cout << a << " " << final_cost << "\n";
        a = max(a, b);
        if (a < final_cost) {
            final_cost = a;
            final_path[0] = tem[i].first.second;
            ga = tem[i].first.first;
            final_path[1] = tem[idx].first.second;
            gb = tem[idx].first.first;
        }
    }
    cout << final_cost << "\n";
    cout << "cost : "<<ga << "\n";
    for (int i : final_path[0]) cout << i << " ";
    cout << "\n";
    cout << "cost : "<<gb << "\n";
    for (int i : final_path[1]) cout << i << " ";

}