#include <iostream>

int main()
{
    int numberOfNodes, valueOfRoad[10][10], roadTaken[10][10];
    std::cout << "input number of nodes: ";
    std::cin >> numberOfNodes;
    std::cout << "input the weight of each road:\n";
    for(int line = 1; line <= numberOfNodes; line++)
        for(int column = 1; column <= numberOfNodes; column++){
            std::cin >> valueOfRoad[line][column];
            if(valueOfRoad[line][column] == 0)
                valueOfRoad[line][column] = 999999;
            if(line == column)
                valueOfRoad[line][column] = 0;
            roadTaken[line][column] = line;
        }
    for(int link = 1; link <= numberOfNodes; link++)
        for(int line = 1; line <= numberOfNodes; line++)
            for(int column = 1; column <= numberOfNodes; column++)
                if(valueOfRoad[line][column] > valueOfRoad[line][link] + valueOfRoad[link][column]){
                    valueOfRoad[line][column] = valueOfRoad[line][link] + valueOfRoad[link][column];
                    roadTaken[line][column] = roadTaken[line][link];
                }
    for(int line = 1; line <= numberOfNodes; line++)
        for(int column = line; column <= numberOfNodes; column++){
            std::cout << column << " ";
            int link = roadTaken[line][column];
            while(link != line){
                std::cout << link << " ";
                link = roadTaken[line][link];
            }
            std::cout << line << "\n";
        }
    return 0;
}