#include <iostream>
        #include <cstdlib>
        #include <deque>

        using namespace std;

        int main(){
                //set
                int path_len[6][6] = {
                        {0, 4, 7, 3, -1, -1},
                        {4, 0, 3, -1, 2, -1},
                        {7, 3, 0, -1, -1, 2},
                        {3, -1, -1, 0, 3, -1},
                        {-1, 2, 2, 3, 0, 2},
                        {-1, 2, -1, 2, -1, 0}
                };
                int close[6], greedy[6], path[6], flag = 0;

                //clear
                for(int i=0;i<6;i++){
                        close[i] = path[i] = 0;
                        greedy[i] = path_len[0][i];
                }

                //start Dijkstra
                int T = 6;
                while(T--){
                        //find min
                        for(int i=0;i<6;i++){
                                if(flag == i || close[i])       continue;

                                if(path_len[flag][i] > 0 && (greedy[i] <= 0 || path_len[flag][i] + greedy[flag] < greedy[i])){
                                        greedy[i] = path_len[flag][i] + greedy[flag];
                                        path[i] = flag;
                                }
                        }
                        close[flag] = 1;
                        //set flag
                        int min = 1000000000;
                        for(int i=0;i<6;i++){
                                if(close[i]) continue;
                                if(greedy[i] > 0 && greedy[i] < min){
                                        min = greedy[i];
                                        flag = i;
                                }
                        }
                }
                //output min
                cout << greedy[5] <<endl;
                //output path
                deque<int> find_path;
                T = 5;
                while(T){
                        find_path.push_front(T);
                        T = path[T];
                }
                while(!find_path.empty()){
                        cout << find_path.front() << " ";
                        find_path.pop_front();
                }
                return 0;
        }