#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <queue>
#include <utility>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int maxn = 200100, minn = 999999999;
int n, m;
vector<pair<int, int>>ls[maxn];
vector<int>noduri;
int d[maxn];
int q[maxn], tata[maxn],adaugat[maxn];

struct comp {
	bool operator()(const long& a, const long& b) const {
		return d[a] > d[b];
	}
};

void prim() {

}


int main() {
	in >> n >> m;
	while (m--) {
		int a, b, c;
		in >> a >> b >> c;
		d[a] = minn;
		d[b] = minn;
		if (!adaugat[a])
			noduri.push_back(a);
		if (!adaugat[b])
			noduri.push_back(b);
		ls[a].push_back({ b,c });
		ls[b].push_back({ a,c });

	}
	d[1] = 0;
	priority_queue<int, vector<int>, comp> q(noduri.begin(), noduri.end());
	while (!q.empty()) {
		int x = q.top();
		q.pop();
		for (auto y : ls[x]) {
			if (tata[y.first] == 0 && y.second < d[y.first]) {
				d[y.first] = y.second;
				tata[y.first] = x;
				q.push(y.first);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << i << " " << tata[i] << "\n";
	}
	return 0;
}