#include<fstream.h>
#define N 200001
#define INF 10000000
typedef struct nod
{long in,co;
nod *urm;}Nod;
long n,m,i,j,k,d[N],w[N],h[N],s,t,e,l[N],r,q[N];
Nod *g[N],*p;

void ad(long h[N],long *n,long p[N],long v[N],long j)
{h[++(*n)]=j,p[j]=(*n);
long t=(*n),k=h[t],x;
while(t>1&&v[k]<v[h[t/2]])
      x=h[t],h[t]=h[t/2],h[t/2]=x,x=p[h[t]],p[h[t]]=p[h[t/2]],p[h[t/2]]=x,t/=2;}

void de(long h[N],long *n,long k,long p[N],long v[N])
{long s,x,t=h[k];
h[k]=h[(*n)],h[(*n)]=t,x=p[h[(*n)]],p[h[(*n)--]]=p[h[k]],p[h[k]]=x,x=h[k];
while(k>1&&v[x]<v[h[k/2]])
      t=p[h[k]],p[h[k]]=p[h[k/2]],p[h[k/2]]=t,t=h[k],h[k]=h[k/2],h[k/2]=t,k/=2;
do
      {s=0;
      if(2*k<=(*n))
            {s=2*k;
            if(2*k<(*n)&&v[h[2*k+1]]<v[h[2*k]])
                   s=2*k+1;
            if(v[h[s]]>=v[h[k]])
                   s=0;}
      if(s)
            x=h[k],h[k]=h[s],h[s]=x,t=p[h[s]],p[h[s]]=p[h[k]],p[h[k]]=t,k=s;}
while(s);}

void pu(Nod *&q,long x,long y)
{Nod *p=new Nod;
p->in=x,p->co=y,p->urm=q,q=p;}

void mo(long h[N],long n,long d[N],long poz[N],long l,long k)
{long i,x,z;
if(k<=d[h[l]])
     {d[h[l]]=k,i=l,z=h[l];
     while(i>1&&d[h[i/2]]>d[z])
            x=h[i],h[i]=h[i/2],h[i/2]=x,x=poz[h[i]],poz[h[i]]=poz[h[i/2]],poz[h[i/2]]=x,i/=2;}}

int main()
{ifstream f("apm.in");
ofstream z("apm.out");
f>>n>>m;
for(j=0;j<n;j++)
     g[j]=NULL,d[j]=INF,q[j]=-1,l[j]=0;
while(m--)
     f>>i>>j>>k,i--,j--,pu(g[i],j,k),pu(g[j],i,k);
d[0]=j=0;
for(i=0;i<n;i++)
     ad(h,&j,w,d,i);
while(j)
     {i=h[1],l[i]=1;
     de(h,&j,w[i],w,d);
     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,mo(h,j,d,w,w[p->in],d[p->in]);}
for(i=0;i<n;i++)
if(q[i]>=0)
     e+=d[i];
z<<e<<"\n"<<(n-1)<<"\n";
for(j=0;j<n;j++)
if(q[j]>=0)
     z<<j+1<<" "<<q[j]+1<<"\n";
return 0;}