#include <bits/stdc++.h>
#define NMAX 400001
using namespace std;
struct nod
{
	int x, y, c;
}v[NMAX];
bool cmp(nod a,nod b)
{
    return (a.c < b.c);
}
int tata[NMAX], s, n, m, i, j, ct, ai, aj;
bool viz[NMAX];
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> n >> m;
    for(i = 1; i <= m; ++ i)
		f >> v[i].x >> v[i].y >> v[i].c;
	sort(v + 1, v + m + 1, cmp);
	for(i = 1; i <= n; ++ i)
        tata[i] = i;
	for(i = 1; i <= m && ct < n - 1; ++ i)
		if(tata[v[i].x] != tata[v[i].y])
		{
		    ct ++;
			viz[i] = true;
			s = s + v[i].c;
			ai = tata[v[i].x];
            aj = tata[v[i].y];
			for(j = 1; j <= n; j ++)
				if(tata[j] == aj) tata[j] = ai;
		}
	g << s << "\n" << ct << "\n";
	for(i = 1; i < m; ++ i)
		if(viz[i] == true)
			g << v[i].x << " " << v[i].y << "\n";
    return 0;
}