#include<stream>

typedef {
    int data[100];
    int n;
} Arr;

typedef {
    int first[100];
    int second[100];
    int n;
} PairArr;

Arr createArr(){ Arr arr; arr.n = 0; return arr }
Arr createPairArr(){ PairArr arr; arr.n = 0; return arr }

Arr pushArr(Arr arr, int x){
    arr.data[arr.n++] = x;
    return arr;
}
Arr pushPairArr(PairArr arr, int first, int second){
    arr.first[arr.n] = first;
    arr.second[arr.n] = second;
    arr.n++;
    return arr;
}
int size(Arr arr){ return arr.n; }
int size(PairArr arr){ return arr.n; }
int indexOf(Arr arr, int x){
    for(int i=0; i<size(arr); i++){
        if(arr.data[i] == x) return i;
    }
    return -1;
}
int contains(Arr arr, int x){
    return indexOf(arr, x) >= 0;
}

typedef {
    int M[100][100];
    int n;
} Metrix;

Metrix createMetrix(){ Metrix m; m.n = 0; return m; }
Metrix addVertex(Metrix m){ m.n++; return m; }
Metrix setPath(Metrix m, int from, int to, weight){
    m.M[from][to] = weight;
    return m;
}
int getWeight(Metrix m, int from, int to){
    return m.M[from][to];
}
Arr getNexts(Metrix m, int from){
    Arr next = createArr();
    for(int i=0; i < m.n; i++){
        if(from == i) continue;
        if(m.M[from][i] == 0) continue;
        arr = push_arr(arr, i);
    }
    return next;
}
PairArr getNextsGroup(Metrix m, Arr froms, Arr visited){
    PairArr next = createPairArr();
    for(int i=0; i < size(froms); i++){
        Arr next2 = getNexts(m, froms.data[i]);
        next2 = filterNotVisit(next2, visited);
        for(int j=0; j<size(next2); j++){
            next = pushPairArr(next, i, next2.data[j]);
        }
    }
    return next;
}
Arr filterNotVisit(Arr next, Arr visited){
    Arr next2 = createArr();
    for(int i=0; i<size(next); i++){
        if(contains(visited, next.data[i])) continue;
        pushArr(next2, next.data[i]);
    }
    return next2;
}

int main(){

    int n = 5;

    Metrix M = createMetrix();
    M = addVertex(M);
    M = addVertex(M);
    M = addVertex(M);
    M = addVertex(M);
    M = setPath(M, 0, 1, 9);

    Arr visited = createArr();
    visited = pushArr(visited, 0);

    PairArr path = createPairArr();

    for(int i=0; i<n - 1; i++){
        PairArr nexts = getNextsGroup(M, visited, visited);
        if(size(nexts) == 0) continue;
        int from = nexts.first[0];
        int to = nexts.second[0];
        for(int j=1; j<size(nexts); j++){
            if(getWeight(M,nexts.first[j], nexts.second[j]) < getWeight(M, from, to)){
                from = nexts.first[j];
                to = nexts.second[j];
            }
        }
        path = pushPairArr(path, from, to);
        visited = pushArr(visited, to);
    }

    for(int i=0; i<size(path); i++){
        cout << path.first[i] << " "<< path.second[i] << " " << getWeight(M,path.first[i], path.second[i]) << endl;
    }

    return 0;
}