#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;
}