#include<stdio.h>
#include<stdlib.h>
int n,m,i,j,k,d[200005],w[200005],h[200005],*g[100005],*f[100005],s,t,e,l[200005],r,q[200005],a[200005],b[200005],c[200005];
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 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);
	for(i=1;i<=m;i++)
    	scanf("%d%d%d",&a[i],&b[i],&c[i]),w[a[i]]++,w[b[i]]++;
    for(i=1;i<=n;w[i++]=0)
        g[i]=f[i]=(int*)malloc(w[i]*sizeof(int));
    for(i=1;i<=m;i++)
        g[a[i]][w[a[i]]]=b[i],g[b[i]][w[b[i]]]=a[i],f[a[i]][w[a[i]]++]=f[b[i]][w[b[i]]++]=c[i];
	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]),j=0;j<w[i];j++)
     	if(!l[g[i][j]]&&f[i][j]<d[g[i][j]])
        	d[g[i][j]]=f[i][j],q[g[i][j]]=i,M(w[g[i][j]],d[g[i][j]]);
	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]);
}