//Arbore partial de cost minim - Algoritmul lui Prim  
#include<fstream.h>  
#include<stdlib.h>  
#define INF 32000  
  
struct vecin_cost  
    {long int v;  
     int c;  
     };  
vecin_cost *A[200001];
int *viz,cmin[200001];
long *scmin,cost,n,m,i,k,x,y;

struct muchie
    {long a,b;
    } vm[200001];

int selmin()
{long h=INF,sel;
for(long i=1;i<=n;++i)
    if(!viz[i])
	if(cmin[i]<h) {h=cmin[i];
		sel=i;
		}
return sel;
}

int main()
{ifstream f("apm.in");
ofstream g("apm.out");
f>>n>>m;
for(i=1;i<=n;++i)
    {A[i]=(vecin_cost *)calloc(1,sizeof(vecin_cost));
    A[i][0].v=0;
    cmin[i]=INF;
    }
scmin=(long *) calloc(n+1,sizeof(long));
viz=(int *) calloc(n+1,sizeof(int));
for(i=1;i<=m;++i)
    {f>>x>>y>>k;
    A[x]=(vecin_cost *)realloc(A[x],(A[x][0].v+2)*sizeof(vecin_cost));
    A[x][++A[x][0].v].v=y;
    A[x][A[x][0].v].c=k;  
    A[y]=(vecin_cost *) realloc(A[y], (A[y][0].v+2)*sizeof(vecin_cost));  
    A[y][++A[y][0].v].v=x;  
    A[y][A[y][0].v].c=k;  
    }  
viz[1]=1;  
for(i=1;i<=A[1][0].v;++i)  
    {cmin[A[1][i].v]=A[1][i].c;  
    scmin[A[1][i].v]=1;  
    }  
for(k=2;k<=n;++k)  
    {  
    x=selmin();  
    cost+=cmin[x];  
    viz[x]=1;  
    vm[++vm[0].a].a=scmin[x];  
    vm[vm[0].a].b=x;  
    for(i=1;i<=A[x][0].v;++i)  
        if(cmin[A[x][i].v]>A[x][i].c) {cmin[A[x][i].v]=A[x][i].c;  
			scmin[A[x][i].v]=x;};
     
    }  
  
g<<cost<<'\n'<<n-1<<'\n';  
for(i=1;i<=vm[0].a;++i)  
    g<<vm[i].a<<' '<<vm[i].b<<'\n';  
f.close();  
g.close();  
return 0;  
}