#include <cstdio>
#include <vector>
#include <algorithm>
#include <fstream>

#define nmax 200005
#define mmax 400005


#define pb push_back


using namespace std;

ifstream fin ("apm.in");
vector <int> V;
int X [mmax], Y [mmax], C [mmax], ind [mmax];
int comp [nmax];
int N, M, sol;
struct cmp
{	
	bool operator () (const int &a, const int &b)
	{
		if (C [a] < C [b]) return 1;
		return 0;
	}
};
int find (int x)
{
	if (comp [x] == x) return x;
	else comp [x] = find (comp [x]);
	return comp [x];
}
void unite (int x, int y) {
	comp [find (x)] = find (y);
}
int main () {
	
	freopen ("apm.out", "w", stdout);
	int i;
	fin >> N >> M;
	for (i = 1; i <= M; i++) {
		fin >> X [i] >> Y [i] >> C [i];
		ind [i] = i;
	}
	for (i = 1; i <= N; i++)
		comp [i] = i;
	sort (ind + 1, ind + M + 1, cmp ());
	for (i = 1; i <= M; i++) 
		if (find (X [ind [i]]) != find (Y [ind [i]])) {
			sol += C [ind [i]];
			unite (X [ind [i]], Y [ind [i]]);
			V.pb (ind [i]);
		}
	printf ("%d\n%d\n", sol, N - 1);
	for (vector <int> :: iterator it = V.begin (); it != V.end (); it++)
		printf ("%d %d\n", X [*it], Y [*it]);
	return 0;
}