#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, val1, val2;
bool viz[NMAX];
int Find(int nod)
{
    while(nod != tata[nod]) nod = tata[nod];
    return nod;
}
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)
    {
        val1 = Find(v[i].x);
        val2 = Find(v[i].y);
		if(val1 != val2)
		{
		    ct ++;
			viz[i] = true;
			s = s + v[i].c;
			tata[val1]=val2;
		}
    }
	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;
}