#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct Edge {
	int x, id, c;
	bool operator < (const Edge &other) const {
		return c > other.c;
	}
};

int n, m, x, y, c, viz[200100], vf, sol[200100];
vector <pair <int, int> > v[200100];
priority_queue <Edge> h;
Edge E[400100];

int main() {
	ios_base::sync_with_stdio();
	in.tie(NULL);
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		in >> x >> y >> c;
		v[x].push_back({y, i});
		v[y].push_back({x, i});
		E[i] = {x, y, c};
	}
	for (auto i : v[1]) 
		h.push({i.fi, i.se, E[i.se].c});
	viz[1] = 1;
	int rs = 0;
	while (!h.empty()) {
		auto e = h.top();
		h.pop();
		if (!viz[e.x]) {
			viz[e.x] = 1;
			rs += e.c;
			sol[++vf] = e.id;
			for (auto nod : v[e.x])
				if (!viz[nod.fi])
					h.push({nod.fi, nod.se, E[nod.se].c});
		}
	}
	out << rs << '\n' << n - 1 << '\n';
	rs = 0;
	for (int i = 1; i < n; i++)
		out << E[sol[i]].x << ' ' << E[sol[i]].id << '\n';
	return 0;
}