typedef {
    int from;
    int to;
    int weight;
} Edge;

void swap(Edge *a, Edge *b){
    Edge *c = a;
    a = b;
    b = c;
}

void sortEdge(Edge edge[], int n){
    for(int i=0; i<n-1; i++){
        for(int j=0; j<n-1; j++){
            if(edge[j].weight > edge[j+1].weight){
                swap(&edge[j], &edge[j+1]);
            }
        }
    }
}

//

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);

    //input
    Arr visited = createArr();
    PairArr path = createPairArr();

    Edge edge[100];
    sort(edge, n);

    int i=0;
    while(size(visited) < n - 1){
        Edge e = edge[i++];
        if(contains(visited, e.from) && contains(visited, e.to)) continue;
        path = pushPairArr(path, e.from, e.to);
        if( ! contains(visited, e.from)) visited = pushArr(visited, e.from);
        if( ! contains(visited, e.to)) visited = pushArr(visited, e.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;
}