/*
Copyright 2012 Marek "p2004a" Rusinowski
Computing MST - Prim's algorithm
*/
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#define MAXN 1000000
#define INF 0x7FFFFFFF
std::vector<std::pair<int, int> > edges[MAXN], out;
int d[MAXN], p[MAXN];
struct cmp {
bool operator() (int a, int b) {
if (d[a] < d[b]) {
return true;
} else if (d[a] > d[b]) {
return false;
} else {
return a < b;
}
}
};
void mst(int n) {
std::set<int, cmp> q;
std::fill(d + 1, d + n, INF);
q.insert(0);
while (!q.empty()) {
int v = *(q.begin());
q.erase(q.begin());
if (v != 0) {
out.push_back(std::make_pair(p[v], v));
}
for (int i = 0; i < (int) edges[v].size(); ++i) {
if (d[edges[v][i].first] > d[v] + edges[v][i].second) {
q.erase(edges[v][i].first);
d[edges[v][i].first] = d[v] + edges[v][i].second;
p[edges[v][i].first] = v;
q.insert(edges[v][i].first);
}
}
}
}
int main() {
int n, m, a, b, c;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; ++i) {
scanf("%d %d %d", &a, &b, &c);
--a, --b;
edges[a].push_back(std::make_pair(b, c));
edges[b].push_back(std::make_pair(a, c));
}
mst(n);
for (int i = 0; i < (int) out.size(); ++i) {
printf("%d %d\n", out[i].first + 1, out[i].second + 1);
}
return 0;
}
LyoKICBDb3B5cmlnaHQgMjAxMiBNYXJlayAicDIwMDRhIiBSdXNpbm93c2tpCiAgQ29tcHV0aW5nIE1TVCAtIFByaW0ncyBhbGdvcml0aG0KKi8KI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCiNkZWZpbmUgTUFYTiAxMDAwMDAwCiNkZWZpbmUgSU5GIDB4N0ZGRkZGRkYKCnN0ZDo6dmVjdG9yPHN0ZDo6cGFpcjxpbnQsIGludD4gPiBlZGdlc1tNQVhOXSwgb3V0OwppbnQgZFtNQVhOXSwgcFtNQVhOXTsKCnN0cnVjdCBjbXAgewogIGJvb2wgb3BlcmF0b3IoKSAoaW50IGEsIGludCBiKSB7CiAgICBpZiAoZFthXSA8IGRbYl0pIHsKICAgICAgcmV0dXJuIHRydWU7CiAgICB9IGVsc2UgaWYgKGRbYV0gPiBkW2JdKSB7CiAgICAgIHJldHVybiBmYWxzZTsKICAgIH0gZWxzZSB7CiAgICAgIHJldHVybiBhIDwgYjsKICAgIH0KICB9Cn07Cgp2b2lkIG1zdChpbnQgbikgewogIHN0ZDo6c2V0PGludCwgY21wPiBxOwogIHN0ZDo6ZmlsbChkICsgMSwgZCArIG4sIElORik7CiAgcS5pbnNlcnQoMCk7CiAgd2hpbGUgKCFxLmVtcHR5KCkpIHsKICAgIGludCB2ID0gKihxLmJlZ2luKCkpOwogICAgcS5lcmFzZShxLmJlZ2luKCkpOwogICAgaWYgKHYgIT0gMCkgewogICAgICBvdXQucHVzaF9iYWNrKHN0ZDo6bWFrZV9wYWlyKHBbdl0sIHYpKTsKICAgIH0KICAgIGZvciAoaW50IGkgPSAwOyBpIDwgKGludCkgZWRnZXNbdl0uc2l6ZSgpOyArK2kpIHsKICAgICAgaWYgKGRbZWRnZXNbdl1baV0uZmlyc3RdID4gZFt2XSArIGVkZ2VzW3ZdW2ldLnNlY29uZCkgewogICAgICAgIHEuZXJhc2UoZWRnZXNbdl1baV0uZmlyc3QpOwogICAgICAgIGRbZWRnZXNbdl1baV0uZmlyc3RdID0gZFt2XSArIGVkZ2VzW3ZdW2ldLnNlY29uZDsKICAgICAgICBwW2VkZ2VzW3ZdW2ldLmZpcnN0XSA9IHY7CiAgICAgICAgcS5pbnNlcnQoZWRnZXNbdl1baV0uZmlyc3QpOwogICAgICB9CiAgICB9CiAgfQp9CgppbnQgbWFpbigpIHsKICBpbnQgbiwgbSwgYSwgYiwgYzsKICBzY2FuZigiJWQgJWQiLCAmbiwgJm0pOwogIGZvciAoaW50IGkgPSAwOyBpIDwgbTsgKytpKSB7CiAgICBzY2FuZigiJWQgJWQgJWQiLCAmYSwgJmIsICZjKTsKICAgIC0tYSwgLS1iOwogICAgZWRnZXNbYV0ucHVzaF9iYWNrKHN0ZDo6bWFrZV9wYWlyKGIsIGMpKTsKICAgIGVkZ2VzW2JdLnB1c2hfYmFjayhzdGQ6Om1ha2VfcGFpcihhLCBjKSk7CiAgfQogIG1zdChuKTsKICBmb3IgKGludCBpID0gMDsgaSA8IChpbnQpIG91dC5zaXplKCk7ICsraSkgewogICAgcHJpbnRmKCIlZCAlZFxuIiwgb3V0W2ldLmZpcnN0ICsgMSwgb3V0W2ldLnNlY29uZCArIDEpOwogIH0KICByZXR1cm4gMDsKfQo=