#include<stdio.h>
#include<stdlib.h>
typedef struct T {
	int I,C;
	struct T *U;
}N;
int n,m,i,j,k,d[200005],w[200005],h[200005],s,t,e,l[200005],r,q[200005];
N *g[200005],*p;
void A(int *n,int j) {
	h[++(*n)]=j,w[j]=*n;
	int t=*n,k=h[t],x;
	while(t>1&&d[k]<d[h[t/2]])
    	x=h[t],h[t]=h[t/2],h[t/2]=x,w[h[t]]=t,w[h[t/2]]=t/2,t/=2;
}
void D(int *n,int k) {
	int s=k,x,t=h[k];
	h[k]=h[*n],h[*n]=t,x=w[h[*n]],w[h[(*n)--]]=w[h[k]],w[h[k]]=x,x=h[k];
	while(k>1&&d[x]<d[h[k/2]])
    	w[h[k]]=k,w[h[k/2]]=k/2,t=h[k],h[k]=h[k/2],h[k/2]=t,k/=2;
	while(1) {
		if(2*k<=*n&&d[h[2*k]]<d[h[s]])
        	s=2*k;
      	if(2*k<*n&&d[h[2*k+1]]<d[h[s]])
            s=2*k+1;
      	if(k==s)
            break;
      	x=h[k],h[k]=h[s],h[s]=x,w[h[s]]=s,w[h[k]]=k,k=s;
	}
}
void P(N *&q,int x,int y) {
	N *p=(N*)malloc(sizeof(N));
	p->I=x,p->C=y,p->U=q,q=p;
}
void M(int l,int k) { for(d[h[l]]=k;l>1&&d[h[l/2]]>k;h[l]^=h[l/2]^=h[l]^=h[l/2],w[h[l]]=l,w[h[l/2]]=l/2,l/=2); }
int main() {
	freopen("apm.in","r",stdin),freopen("apm.out","w",stdout),scanf("%d%d",&n,&m);
	while(m--)
    	scanf("%d%d%d",&i,&j,&k),P(g[i],j,k),P(g[j],i,k);
	for(j=1,A(&j,1),i=2;i<=n;i++)
    	d[i]=1000000,A(&j,i);
	while(j)
     	for(i=h[1],l[i]=1,D(&j,w[i]),p=g[i];p;p=p->U)
     	if(!l[p->I]&&p->C<d[p->I])
        	d[p->I]=p->C,q[p->I]=i,M(w[p->I],d[p->I]);
	for(i=1;i<=n;i++)
	if(q[i])
    	e+=d[i];
	printf("%d\n%d\n",e,n-1);
	for(j=1;j<=n;j++)
	if(q[j])
     	printf("%d %d\n",j,q[j]);
}