#include <bits/stdc++.h>

using namespace std;

const int nMax = 2e5 + 2;

const int INF = 1e9;

int n, m, d[nMax];
vector<pair<int, int>>g[nMax];
set<pair<int, int>>s;
bool used[nMax];
int from[nMax];

void Bagavecini(int nod) {
	for (const auto& i : g[nod]) {
		if (i.second < d[i.first] && !used[i.first]) {
			s.erase({d[i.first], i.first});
			d[i.first] = i.second;
			s.insert({d[i.first], i.first});
			from[i.first] = nod;
		}
	}
}

int main() {
	ifstream cin("apm.in");
	ofstream cout("apm.out");

	cin >> n >> m;

	for (int i = 1, x, y, c; i <= m; ++i) {
		cin >> x >> y >> c;
		g[x].emplace_back(y, c);
		g[y].emplace_back(x, c);
	}

	for (int i = 1; i <= n; ++i)
		d[i] = INF;

	Bagavecini(1);
	used[1] = true;
	vector<pair<int, int>>sol;

	while (!s.empty()) {
		auto nod = s.begin();
		sol.emplace_back(nod->second, from[nod->second]);
		used[nod->second] = 1;
		s.erase(nod);
		Bagavecini(nod->second);
	}

	int cost = 0;

	for (int i = 2; i <= n; ++i)
		cost += d[i];

	cout << cost << '\n' << n - 1<< '\n';

	for (int i = 0; i < n - 1; ++i)
		cout << sol[i].first << ' ' << sol[i].second << '\n';
}