#include<cstdio>
typedef struct nod
{int in,co;
nod *urm;}Nod;
int n,m,i,j,k,d[200005],w[200005],h[200005],s,t,e,l[200005],r,q[200005];
Nod *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(Nod *&q,int x,int y)
{Nod *p=new Nod;
p->in=x,p->co=y,p->urm=q,q=p;}

void M(int l,int k)
{d[h[l]]=k;
while(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);
j=1,A(&j,1);
for(i=2;i<=n;i++)
     d[i]=1000000,A(&j,i);
while(j)
     {i=h[1],l[i]=1,D(&j,w[i]);
     for(p=g[i];p;p=p->urm)
     if(!l[p->in]&&p->co<d[p->in])
           d[p->in]=p->co,q[p->in]=i,M(w[p->in],d[p->in]);}
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]);
return 0;}