#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 1, INF = 1e9;
vector<pair<int, int>> mc[N];
int t[N], d[N], connected[N];
vector<pair<int, int>> ans;
int n, m, x, y, c, total;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

void djk() {
	pq.push({ 0, 1 });

	for (int i = 2; i <= n; ++i) d[i] = INF;
	
	while (!pq.empty()) {
		int cost = pq.top().first, nod = pq.top().second;
		pq.pop();

		if (t[nod] == 1) continue;

		t[nod] = 1;
		total += d[nod];
		if (nod != 1) {
			ans.push_back({ connected[nod], nod });
		}

		for (auto& i : mc[nod]) {
			if (t[i.first] != 1 && d[i.first] > i.second) {
				d[i.first] = i.second;
				connected[i.first] = nod;
				pq.push({ i.second, i.first });
			}
		}
	}
}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;

	while (m--) {
		cin >> x >> y >> c;
		
		mc[x].push_back({ y, c });
		mc[y].push_back({ x, c });
	}

	djk();

	cout << total << '\n';
	cout << ans.size() << '\n';
	for (auto& i : ans) cout << i.first << ' ' << i.second << '\n';

	return 0;
}