#include <bits-stdc++.h>
using namespace std;

struct pd {
public:
	int to, from, length;

	bool operator<(const pd& elem) const {
		return length > elem.length;
	}
};

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	vector<pair<int, int>> elem[20000];
	int n, m;
	cin >> n >> m;
	while (--m >= 0) {  //  read values
		int x, y, length;
		cin >> x >> y >> length;
		elem[x].push_back(make_pair(y, length));
		elem[y].push_back(make_pair(x, length));
	}

	priority_queue<pd> list;
	vector<bool> finded(n + 1);
	vector<int> result(n + 1);
	int minimSum = 0;
	list.push(pd {1, 0, 0});
	
	while (list.size()) {
		pd act = list.top();
		list.pop();
		if (finded[act.to]) {  //  if element have been used
			continue;
		}
		int from = act.to;
		minimSum += act.length;
		finded[from] = true;
		result[from] = act.from;
		for (pair<int, int> to : elem[from]) {
			list.push(pd{ to.first, from, to.second });  //  add all near elements
		}
	}
	cout << minimSum << '\n' << n - 1;
	for (int i = 2; i <= n; ++i) {
		cout << '\n' << i << ' ' << result[i];
	}
	return 0;
}