#include<iostream>
#include<fstream>
 
using namespace std;

typedef struct m{
	int x,y,c;
} muchie;

muchie M[400001],vec[400001];
int color[200001];
void merge (int a, int q, int b)
    {
        int i=0,p1,p2;
        p1=a; p2=q+1;
         
        while (p1<=q || p2<=b)
            if (p1<=q && p2<=b)
                if (M[p1].c<=M[p2].c)
                    vec[++i]=M[p1++];
                else
                    vec[++i]=M[p2++];
            else if (p1<=q)
                vec[++i]=M[p1++];
            else
                vec[++i]=M[p2++];
         
        for (i=a; i<=b; i++)
            M[i]=vec[i-a+1];
    }
 
 
void sort (int a, int b)
    {   int q;
        if (a<b)
            {
                q=(a+b)/2;
                sort (a,q);
                sort (q+1,b);
                merge (a,q,b);
            }
    }
 
int main()
{
    int n,i,m,nrm=0,j,iz,x,y,cost=0,pas=0;
    ifstream f("apm.in");
    ofstream g("apm.out");
     
    f>>n>>m;
	iz=n; //nr de noduri izolate
    for (i=1; i<=m; i++)
		f>>M[i].x>>M[i].y>>M[i].c;

    sort (1,m);
	
	while (iz>0){
		pas++;
		x=M[pas].x;
		y=M[pas].y;
		if (color[x]==0 && color[y]==0){
			iz-=2;
			color[x]=color[y]=pas;
			nrm++;
			vec[pas].c=-1;
			cost+=M[pas].c;
		}
		else if (color[x]==0 && color[y]!=0){
			iz-=1;
			color[x]=color[y];
			nrm++;
			vec[pas].c=-1;
			cost+=M[pas].c;
		}
		else if (color[x]!=0 && color[y]==0){
			iz-=1;
			color[y]=color[x];
			nrm++;
			vec[pas].c=-1;
			cost+=M[pas].c;
		}
		else if (color[x]!=color[y]){
			for (j=1; j<=n; j++)
				if (color[j]==color[y] && j!=y) color[j]=color[x];
			color[y]=color[x];
			nrm++;
			vec[pas].c=-1;
			cost+=M[pas].c;
		}
	}
	
	g<<cost<<"\n"<<nrm<<"\n";
	for (i=1; i<=pas; i++)
		if (vec[i].c==-1)
			g<<vec[i].x<<" "<<vec[i].y<<"\n";
    return 0;
}