#include <fstream>
#include <vector>
#include <deque>
#include <queue>

using namespace std;

const int NMAX = 2e5 + 10;
const int inf = 1e9;
vector < pair < int, int > > v[NMAX];
int viz[NMAX];

int parent[NMAX], dist[NMAX];

int main() {
	ifstream f("apm.in");
	ofstream g("apm.out");
	
	int n, m;
	f >> n >> m;
	while (m--) {
		int x, y, z;
		f >> x >> y >> z;
		v[x].push_back({ y, z });
		v[y].push_back({ x, z });
	}

	priority_queue < pair < int, int> >q;

	for (int i = 2; i <= n; i++)
		dist[i] = inf;

	q.push({ 0, 1 });
	while (!q.empty()) {
		int node = q.top().second;
		q.pop();

		if (viz[node])
			continue;
		viz[node] = 1;

		for (auto it : v[node]) {
			if (viz[it.first]) continue;
			if (dist[it.first] > it.second) {
				q.push({ -it.second, it.first });
				dist[it.first] = it.second;
				parent[it.first] = node;
			}
		}
	}

	vector < pair < int, int > > vans;
	long long ans = 0;
	for (int i = 2; i <= n; i++) {
		ans += dist[i];
		vans.push_back({ i, parent[i] });
	}
	g << ans << "\n" << vans.size() << "\n";
	for (auto it : vans)
		g << it.first << " " << it.second << "\n";

	return 0;
}