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

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

muchie M[400001],vec[400001];
int indice[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,x,y,cost=0,pas=0,nrc=0;
	int c[100001];
    ifstream f("apm.in");
    ofstream g("apm.out");
     
    f>>n>>m;
    for (i=1; i<=m; i++)
		f>>M[i].x>>M[i].y>>M[i].c;

    sort (1,m);
	for (i=1; i<=n; i++) c[i]=i;
	
	
	while (nrm<n-1){
		pas++;
		x=M[pas].x;
		y=M[pas].y;
		if (c[indice[x]]==0 && c[indice[y]]==0){
			nrc++;
			c[nrc]=nrc;
			indice[x]=indice[y]=nrc;
			
			//c[x]=pas;
			nrm++;
			vec[pas].c=-1;
			cost+=M[pas].c;
		}
		else if (c[indice[x]]==0 && c[indice[y]]!=0){
			indice[x]=indice[y];
			nrm++;
			vec[pas].c=-1;
			cost+=M[pas].c;
		}
		else if (c[indice[x]]!=0 && c[indice[y]]==0){
			indice[y]=indice[x];
			nrm++;
			vec[pas].c=-1;
			cost+=M[pas].c;
		}
		else if (c[indice[x]]!=c[indice[y]]){
			//for (j=1; j<=n; j++)
			//	if (color[j]==color[y] && j!=y) color[j]=color[x];
			//color[y]=color[x];
			c[indice[y]]=c[indice[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;
}