#include <cstdio>
using namespace std;
const int nd=200005;
const int inf=1999999999;
struct nod{int val; int cost; nod *urm;}*p[nd];
int sol,dad[nd],dist[nd],heap[nd],lgheap,n,m,poz[nd];
bool viz[nd];
void read()
{ int i,x,y,c;
  nod *aux;
freopen("apm.in","r",stdin); scanf("%d %d\n",&n,&m);
for(i=1;i<=m;++i)
    {
    scanf("%d %d %d\n",&x,&y,&c);
    aux=new nod; aux->val=y; aux->cost=c; aux->urm=p[x]; p[x]=aux;
    aux=new nod; aux->val=x; aux->cost=c; aux->urm=p[y]; p[y]=aux;
    }
fclose(stdin);
}
void reconstruct_heap()
{ int tata,fiu,z;
  bool e;
poz[heap[1]]=-1; heap[1]=heap[lgheap]; poz[heap[1]]=1; --lgheap;
tata=1; fiu=2; e=true;
while(fiu<=lgheap&&e)
    {
    e=false;
    if(fiu+1<=lgheap&&dist[heap[fiu]]>dist[heap[fiu+1]])++fiu;
    if(dist[heap[fiu]]<dist[heap[tata]])
                    {
                    z=poz[heap[fiu]]; poz[heap[fiu]]=poz[heap[tata]]; poz[heap[tata]]=z;
                    z=heap[fiu]; heap[fiu]=heap[tata]; heap[tata]=z;
                    e=true;
                    tata=fiu; fiu=tata*2;
                    }
    }
}
void upinheap(int ind)
{ bool e;
  int fiu,tata,z;
fiu=poz[ind]; tata=fiu/2; e=true;
while(tata>=1&&e)
    {
    e=false;
    if(dist[heap[fiu]]<dist[heap[tata]])
            {
            z=poz[heap[fiu]]; poz[heap[fiu]]=poz[heap[tata]]; poz[heap[tata]]=z;
            z=heap[fiu]; heap[fiu]=heap[tata]; heap[tata]=z;
            e=true;
            fiu=tata; tata=fiu/2;
            }
    }
}
void prim()
{ int i,ind;
  nod *aux;
for(i=1;i<=n;++i)
    {
    heap[i]=i;
    poz[i]=i;
    dist[i]=inf;
    dad[i]=inf;
    viz[i]=1;
    }
dist[1]=0; lgheap=n;
while(lgheap>0)
    {
    ind=heap[1]; viz[ind]=0;
    reconstruct_heap();
    aux=p[ind];
    while(aux!=NULL)
        {
        if(dist[aux->val]>aux->cost&&viz[aux->val]==1)
                                {
                                dist[aux->val]=aux->cost;
                                dad[aux->val]=ind;
                                upinheap(aux->val);
                                }
        aux=aux->urm;
        }
    }
for(i=1;i<=n;++i)sol+=dist[i];
}
void write()
{ int i;
freopen("apm.out","w",stdout); printf("%d\n",sol); printf("%d\n",n-1);
for(i=2;i<=n;++i)
    printf("%d %d\n",dad[i],i);
fclose(stdout);
}
int main()
{
read();
sol=0;
prim();
write();
return 0;
}