#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <set>
#include <random>
#include <deque>

using namespace std;

void print(vector<int> data) {
    for (auto elem : data) {
        cout << elem << " ";
    }
    cout << " TEMPLAR\n";
}

class Graph {
public:
    int vertices;
    vector<set<int>> adjacency_set;
    vector<int>* cyc;

public:
    Graph() {}

    Graph(int number_vertices, vector<vector<int>> graph) {
        vertices = number_vertices;
        adjacency_set.resize(vertices);
        for (int i = 0; i < vertices; i++) {
            adjacency_set[i] = set<int>();
        }
        for (int i = 0; i < number_vertices; i++) {
            for (size_t j = 0; j < graph[i].size(); j++) {
                adjacency_set[i].insert(graph[i][j]);
            }
        }
    }
    /*
    int get_number_vertices() {
    return vertices;
    }

    int get_numbers_edges() {
    int result = 0;
    for (int i = 0; i < vertices; i++) {
    result += adjacency_set[i].size();
    }
    return result;
    }

    bool is_neighbors(int first, int second) {
    return adjacency_set[first].find(second) != adjacency_set[first].end();
    }

    set<int> get_neighbors(int vert) {
    return adjacency_set[vert];
    }

    int get_number_neighbors(int vert) {
    return adjacency_set[vert].size();
    }

    int get_number_component();
    */
    void is_cycle();

    void is_dic();

    void Dijkstra(int start, int finish) {
        int BIG = 100000 + 1;
        vector<int>* dist = new vector<int>(vertices);
        for (int i = 0; i < vertices; i++) {
            (*dist)[i] = BIG;
        }
        vector<int>* vertic = new vector<int>(vertices);
        set<int>* was = new set<int>;
        (*dist)[start] = 0;
        while (true) {
            int min_dist = BIG;
            int min_vert;
            for (int i = 0; i < vertices; i++) {
                if ((*dist)[i] < min_dist && was->find(i) == was->end()) {
                    min_dist = dist->at(i);
                    min_vert = i;
                    break;
                }
            }
            if (min_dist == BIG) {
                break;
            }
            int v = min_vert;
            was->insert(v);
            for (int vert : adjacency_set[v]) {
                if (dist->at(v) + 1 < dist->at(vert)) {
                    dist->at(vert) = dist->at(v) + 1;
                    vertic->at(vert) = v;
                }
            }
        }
        if (dist->at(finish) != BIG) {
            if (dist->at(finish)) {
                cout << dist->at(finish) << "\n";
                vector<int> res(dist->at(finish) + 1);
                int i = dist->at(finish);
                res[i] = finish + 1;
                int extra = finish;
                while (i != 0) {
                    res[i - 1] = (*vertic)[extra] + 1;
                    extra = (*vertic)[extra];
                    i--;
                }
                print(res);
            } else {
                cout << 0 << " zerowayTEMPLARIN" << '\n';
            }
        } else {
            cout << -1 << " NOTEMPLAR" << '\n';
        }
    }
};

class superGraph {
 private:
    int size_g;
    std::vector<std::vector<int>> data;
    std::vector<int> used;

 public:
    std::vector<bool> isused;
    std::vector<int> distance;
    bool isisdouble = true;
    bool isiscycle = false;
    std::vector<int> cyclepath;
    std::unordered_map<int, int> parents;
    int max_path = 0;

    superGraph() {
    }

    explicit superGraph(int n) {
        data.resize(n);
        isused.resize(n);
        size_g = n;
    }

    void insert(int a, int b) {
        if (a != b) {
            data[a - 1].push_back(b);
            data[b - 1].push_back(a);
        }
    }

    explicit superGraph(std::vector<std::vector<int>> graph) {
        isused.resize(graph.size());
        size_g = graph.size();
        data = graph;
    }

    void printgraph() {
        for (int i = 0; i < data.size(); i++) {
            for (auto j : data[i]) {
                std::cout << j << " ";
            }
            std::cout << '\n';
        }
    }

    void Dijkstra(int a, int b) {
        isused.clear();
        isused.resize(size_g);
        isused[a - 1] = true;
        std::vector<int> result;
        std::vector<int> way;
        std::vector<std::vector<int>> ways;
        ways.resize(size_g);
        result = data[a - 1];
        int v;
        for (int i = 0; i < size_g; i++) {
            if (result[i] != 200000) {
                ways[i].push_back(i + 1);
            }
        }
        for (int j = 0; j < size_g; j++) {
            v = -1;
            for (int i = 0; i < size_g; i++) {
                if (!isused[i] && ((v == -1) || result[v] > result[i])) {
                    v = i;
                }
            }
            if (v == -1) {
                v = size_g - 1;
            }
            isused[v] = true;
            for (int i = 0; i < size_g; i++) {
                if (result[i] > result[v] + data[i][v]) {
                    ways[i].clear();
                    ways[i].insert(ways[i].end(), ways[v].begin(), ways[v].end());
                    ways[i].push_back(i + 1);
                    result[i] = result[v] + data[v][i];
                }
            }
        }

        if (result[b - 1] <= 0 || result[b - 1] == 200000) {
            std::cout << -1 << " NODZHAM" << '\n';
        } else {
           std::cout << result[b - 1] << "\n";
           std::cout << a;
           for (auto i : ways[b - 1]) {
              std::cout << " " << i;
           }
           std::cout << " DZHAM" << '\n';
        }
    }
};

int main() {
    int N, M;
    int a, b;
    std::cin >> N;
    if (N != 0) {
        std::vector<std::vector<int>> dat;
        std::vector<std::vector<int>> ebala;
        ebala.resize(N);
        std::vector<int> line;
        //for (int i = 0; i < N; i++) {
        //    for (int j = 0; j < N; j++) {
        //        std::cin >> a;
        //        if (a == 0) {
        //            line.push_back(200000);
        //        } else {
        //            line.push_back(a);
        //        }
        //    }
        //    dat.push_back(line);
        //    line.clear();
        //}
        std::vector<int> zerosones;
        zerosones.push_back(0);
        zerosones.push_back(0);
        zerosones.push_back(0);
        zerosones.push_back(0);
        zerosones.push_back(1);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                a = zerosones[rand() % 5];
                if (a == 0) {
                    line.push_back(200000);
                } else {
                    line.push_back(a);
                    if (i <= j) {
                        ebala[i].push_back(j);
                        ebala[j].push_back(i);
                    }
                }
            }
            dat.push_back(line);
            line.clear();
        }
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                dat[j][i] = dat[i][j];
            }
        }
        for (int i = 0; i < N; i++) {
            std::cout << i + 1 << ":\t";
            for (int j = 0; j < N; j++) {
                if (dat[i][j] == 200000) {
                    std::cout << 0 << '\t';
                } else {
                    std::cout << dat[i][j] << '\t';
                }
            }
            std::cout << '\n';
        }
        superGraph graph(dat);
        Graph gr(N, ebala);
        for (int i = 0; i < 10; i++) {
            a = rand() % N;
            b = rand() % N;
            if (a == b) {
                std::cout << 0 << "zerowayDZHAM\n";
                std::cout << 0 << "zerowayTEMPLAR\n";
            } else {
                graph.Dijkstra(a + 1, b + 1);
                gr.Dijkstra(a, b);
            }
        }
    }
}