7

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>

using namespace std;

int array[13][13] = {
    {0, 4, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 7, 8, 11, 0, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 6, 10, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 8, 9, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 11, 6, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 8, 12, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 10, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 9, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 7, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
int dynamic[13];

int main(void) {
    for (int i = 1; i < 13; ++ i) {
        for (int j = 0; j < 13; ++ j) {
            if (array[j][i] != 0) {
                if (dynamic[i] == 0) {
                    dynamic[i] = dynamic[j] + array[j][i];
                }
                else {
                    dynamic[i] = min(dynamic[j] + array[j][i], dynamic[i]);
                }
            }
        }
    }

    vector<int> back;
    int x = 12;

    while (x != 0) {
        for (int i = x; i >= 0; -- i) {
            if (array[i][x] != 0 && dynamic[x] == dynamic[i] + array[i][x]) {
                back.push_back(x + 1);
                x = i;
            }
        }
    }
    back.push_back(1);
    reverse(back.begin(), back.end());
    for (int i = 0; i < back.size(); ++ i) {
        cout << back[i] << " ";
    }
    cout << endl;
    cout << dynamic[12] << endl;
    return 0;
}