#define ll long long

#define boolean int
#define false 0
#define true 1

#define MAX_VERTICES 5000

#include <stdio.h>
#include <mm_malloc.h>
#include <limits.h>

#define MAX_LENGTH INT_MAX

typedef enum {
    SUCCESS,
    OUT_OF_MEMORY,
    BAD_NUMBER_VERTICES,
    BAD_NUMBER_EDGES,
    BAD_VERTEX,
    BAD_LENGTH,
    BAD_INPUT,
    NO_SPAN_TREE
} ExitCodes;

const char* exitMessages[] = {
        "success",
        "out of memory",
        "bad number of vertices",
        "bad number of edges",
        "bad vertex",
        "bad length",
        "bad number of lines",
        "no spanning tree"
};

typedef struct _list List;

struct _list {
    int vertice;
    int length;
    List* next;
};

typedef struct _edge Edge;

struct _edge {
    int v1;
    int v2;
    ll priority;
};

void swap(void* first, void* second, size_t size) {
    for (size_t i = 0; i < size; i++) {
        char temp = *((char*)(first) + i);
        *((char*)(first) + i) = *((char*)(second) + i);
        *((char*)(second) + i) = temp;
    }
}

ExitCodes checkInput(int v, int e) {
    if (v < 0 || v > MAX_VERTICES) {
        return BAD_NUMBER_VERTICES;
    }

    if (e < 0 || e > v * (v + 1) / 2) {
        return BAD_NUMBER_EDGES;
    }

    return SUCCESS;
}

ExitCodes fillGraph(List** arrayOfLists, int vertices, int edges) {
    for (int i = 0; i < edges; i++) {
        int v1, v2;
        long long length;
        if (scanf("%d%d%lli", &v1, &v2, &length) < 3) {
            return BAD_INPUT;
        }

        if ((v1 < 1 || v1 > vertices) || (v2 < 1 || v2 > vertices)) {
            return BAD_VERTEX;
        }

        if (length < 0 || length > MAX_LENGTH) {
            return BAD_LENGTH;
        }

        if (!arrayOfLists[v1 - 1]) {
            arrayOfLists[v1 - 1] = (List*)calloc(1, sizeof(List));
            arrayOfLists[v1 - 1] -> vertice = v2 - 1;
            arrayOfLists[v1 - 1] -> length = (int)length;
        } else {
            List* newList = (List*)calloc(1, sizeof(List));
            newList -> vertice = v2 - 1;
            newList -> length = (int)length;
            newList -> next = arrayOfLists[v1 - 1];
            arrayOfLists[v1 - 1] = newList;
        }

        if (!arrayOfLists[v2 - 1]) {
            arrayOfLists[v2 - 1] = (List*)calloc(1, sizeof(List));
            arrayOfLists[v2 - 1] -> vertice = v1 - 1;
            arrayOfLists[v2 - 1] -> length = (int)length;
        } else {
            List* newList = (List*)calloc(1, sizeof(List));
            newList -> vertice = v1 - 1;
            newList -> length = (int)length;
            newList -> next = arrayOfLists[v2 - 1];
            arrayOfLists[v2 - 1] = newList;
        }
    }

    return SUCCESS;
}

boolean checkSpanTree(List** arrayOfLists, int vertices) {
    if (vertices == 0) {
        return false;
    } else if (vertices == 1) {
        return true;
    }

    for (int i = 0; i < vertices; i++) {
        if (!arrayOfLists[i]) {
            return false;
        }
    }

    return true;
}

ExitCodes PrimAlgorithm(List** arrayOfLists, int vertices) {
    Edge* pQueue = (Edge*)calloc((size_t)vertices, sizeof(Edge));
    int* indexes = (int*)calloc((size_t)vertices, sizeof(int));
    int* arrVertices = (int*)calloc((size_t)vertices, sizeof(int));
    boolean* used = (boolean*)calloc((size_t)vertices, sizeof(boolean));
    if (!pQueue || !indexes || !arrVertices || !used) {
        return OUT_OF_MEMORY;
    }

    for (int i = 0; i < vertices; i++) {
        pQueue[i].v1 = vertices;
        pQueue[i].v2 = vertices;
        pQueue[i].priority = (i == 0 ? 0 : (ll)MAX_LENGTH + 1);
        indexes[i] = i;
        arrVertices[i] = i;
        used[i] = false;
    }

    int size = vertices;
    for (int i = 0; i < vertices; i++) {
        if (i > 0) {
            printf("%d %d\n", pQueue[0].v1 + 1, pQueue[0].v2 + 1);
        }

        used[arrVertices[0]] = true;
        swap(&pQueue[0], &pQueue[size - 1], sizeof(Edge));
        swap(&indexes[arrVertices[0]], &indexes[arrVertices[size - 1]], sizeof(int));
        swap(&arrVertices[0], &arrVertices[size - 1], sizeof(int));
        size--;

        int index = 0;
        while (2 * index + 1 < size) {
            if (2 * index + 2 >= size) {
                if (pQueue[index].priority > pQueue[2 * index + 1].priority) {
                    swap(&pQueue[index], &pQueue[2 * index + 1], sizeof(Edge));
                    swap(&indexes[arrVertices[index]], &indexes[arrVertices[2 * index + 1]], sizeof(int));
                    swap(&arrVertices[index], &arrVertices[2 * index + 1], sizeof(int));

                    index = 2 * index + 1;
                } else {
                    break;
                }
            } else {
                if (pQueue[2 * index + 1].priority < pQueue[2 * index + 2].priority) {
                    if (pQueue[index].priority > pQueue[2 * index + 1].priority) {
                        swap(&pQueue[index], &pQueue[2 * index + 1], sizeof(Edge));
                        swap(&indexes[arrVertices[index]], &indexes[arrVertices[2 * index + 1]], sizeof(int));
                        swap(&arrVertices[index], &arrVertices[2 * index + 1], sizeof(int));

                        index = 2 * index + 1;
                    } else {
                        break;
                    }
                } else {
                    if (pQueue[index].priority > pQueue[2 * index + 2].priority) {
                        swap(&pQueue[index], &pQueue[2 * index + 2], sizeof(Edge));
                        swap(&indexes[arrVertices[index]], &indexes[arrVertices[2 * index + 2]], sizeof(int));
                        swap(&arrVertices[index], &arrVertices[2 * index + 2], sizeof(int));

                        index = 2 * index + 2;
                    } else {
                        break;
                    }
                }
            }
        }

        /*for (int j = 0; j < vertices; j++) {
            printf("%d %d %lli\n", pQueue[j].v1, pQueue[j].v2, pQueue[j].priority);
        }
        printf("\n");*/

        for (List* cur = arrayOfLists[arrVertices[size]]; cur; cur = cur -> next) {
            if (used[cur -> vertice]) {
                continue;
            }

            if (pQueue[indexes[cur -> vertice]].priority > cur -> length) {
                pQueue[indexes[cur -> vertice]].v1 = cur -> vertice;
                pQueue[indexes[cur -> vertice]].v2 = arrVertices[size];
                pQueue[indexes[cur -> vertice]].priority = cur -> length;

                int curIndex = indexes[cur -> vertice];
                while (curIndex > 0) {
                    if (pQueue[curIndex].priority < pQueue[(curIndex - 1) / 2].priority) {
                        swap(&pQueue[curIndex], &pQueue[(curIndex - 1) / 2], sizeof(Edge));
                        swap(&indexes[arrVertices[curIndex]], &indexes[arrVertices[(curIndex - 1) / 2]], sizeof(int));
                        swap(&arrVertices[curIndex], &arrVertices[(curIndex - 1) / 2], sizeof(int));

                        curIndex /= 2;
                    } else {
                        break;
                    }
                }
            }
        }

        /*for (int j = 0; j < vertices; j++) {
            printf("%d %d %lli\n", pQueue[j].v1, pQueue[j].v2, pQueue[j].priority);
        }
        printf("\n");*/
    }

    return SUCCESS;
}

ExitCodes start() {
    int vertices, edges;
    if (scanf("%d%d", &vertices, &edges) < 2) {
        return BAD_INPUT;
    }

    ExitCodes currentAction;
    if ((currentAction = checkInput(vertices, edges)) != SUCCESS) {
        return currentAction;
    }

    List** arrayOfLists = (List**)calloc((size_t)vertices, sizeof(List*));
    if (!arrayOfLists) {
        return OUT_OF_MEMORY;
    }

    if ((currentAction = fillGraph(arrayOfLists, vertices, edges)) != SUCCESS) {
        return currentAction;
    }

    if (!checkSpanTree(arrayOfLists, vertices)) {
        return NO_SPAN_TREE;
    }

    if ((currentAction = PrimAlgorithm(arrayOfLists, vertices)) != SUCCESS) {
        return currentAction;
    }

    return SUCCESS;
}

int main() {
    ExitCodes exec;
    if ((exec = start()) != SUCCESS) {
        printf("%s", exitMessages[exec]);
    }

    return exec;
}