// Momentul cela cand sursa oficiala ia 90 ...
#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

#define dim 10001
char buff[dim];
int pos = 0;

void read (int &nr) {
	nr = 0;
	while ((buff[pos] < '0' || buff[pos] > '9') && buff[pos] != '-')
		if (++pos == dim) 
			fread(buff, 1, dim, stdin), pos = 0;
	int semn = 1;
	if (buff[pos] == '-') {
		semn = -1;
		if (++pos == dim) 
			fread(buff, 1, dim, stdin), pos = 0;
	}
	while (buff[pos] >= '0' && buff[pos] <= '9') {
		nr = 10 * nr + buff[pos] - '0';
		if (++pos == dim) 
			fread(buff, 1, dim, stdin), pos = 0;
	}
	nr *= semn;
}

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() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	read(n);
	read(m);
	for (int i = 1; i <= m; i++) {
		read(x);
		read(y);
		read(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});
		}
	}
	cout << rs << '\n' << n - 1 << '\n';
	rs = 0;
	for (int i = 1; i < n; i++)
		cout << E[sol[i]].x << ' ' << E[sol[i]].id << '\n';
	return 0;
}