#include<stdio.h>   
#define nmax 200010   

long h[nmax], vz[nmax], n, m, nh;  

struct elem   
{   
	long vf, c;   
    elem *urm;   
}   *a[nmax], *q;  

struct muchie   
{       
	long x, y;   
}   t[nmax]; 

FILE *f, *g;   
  
void read()   
{   
	long i, x, y, c;   
    fscanf(f, "%ld%ld", &n, &m);   
    for(i=1; i<=m; i++)   
    {   
		fscanf(f, "%ld%ld%ld", &x, &y, &c);   
        q=new elem;   
        q->vf=x; q->c=c; q->urm=a[y];   
        a[y]=q;   
        q=new elem;   
        q->vf=y; q->c=c; q->urm=a[x];   
        a[x]=q;   
    }   
}   
  
void ins(long x, long y, long c)   
{   
	long k, z;   
    muchie tmp;   
    nh++; k=nh;   
    h[nh]=c; t[nh].x=x; t[nh].y=y;   
    while(h[k/2]>h[k] && k>1)   
    {   
		z=h[k/2]; h[k/2]=h[k]; h[k]=z;   
        tmp=t[k/2]; t[k/2]=t[k]; t[k]=tmp;   
        k=k/2;   
    }   
}   
  
void del(long k)   
{       
	long z, m;   
    muchie tmp;   
    z=h[nh]; h[nh]=h[k]; h[k]=z;   
    tmp=t[nh]; t[nh]=t[k]; t[k]=tmp;   
    nh--;   
    while( ((h[k]>h[2*k] && 2*k<=nh) || (h[k]>h[2*k+1] && 2*k+1<=nh)) && k<nh)   
    {       
		if(2*k==nh)         
			m=2*k;   
        else    
			if(h[2*k]<h[2*k+1])     
				m=2*k;   
            else            
				m=2*k+1;   
        z=h[m]; h[m]=h[k]; h[k]=z;   
        tmp=t[m]; t[m]=t[k]; t[k]=tmp;   
        k=m;   
    }   
}   
  
  
int main()   
{       
	long i, x, o=0, nr=0;   
    muchie sol[nmax];   
    f=fopen("apm.in", "r");   
    g=fopen("apm.out", "w");   
    read();   
    sol[0].x=0; sol[0].y=0;   
    x=1; vz[x]=1;   
    do   
    {   
		for(q=a[x]; q; q=q->urm)   
            if(!vz[q->vf])   
                ins(x, q->vf, q->c);   
        while(vz[t[1].y] && nh)   
            del(1);   
        if(nh)   
        {   
			o++;   
            sol[o].x=t[1].x; sol[o].y=t[1].y;   
            nr+=h[1];   
            vz[t[1].y]=1;   
            x=t[1].y;   
            del(1);   
        }   
    }   
    while(nh);   
    fprintf(g, "%ld\n%ld\n", nr, o);   
    for(i=1; i<=o; i++)   
        fprintf(g, "%ld %ld\n", sol[i].x, sol[i].y);   
    return 0;   
}