#include<stdio.h>
#include<stdlib.h>
#define N 200001
#define M 400001
#define INF 10000000
typedef struct nod
{long info,cost;
struct nod *urm;}Nod,*list;
long n,m,i,j,k,a,b,c,d[N],poz[N],h[N],s,t,e=0,l[N],r,par[N],min;
list g[N],p;

void add(long h[N],long *n,long poz[N],long v[N],long j)
{(*n)++;
h[(*n)]=j;
poz[j]=(*n);
long t=(*n),key,x,y;
key=h[t];
while(t>1&&v[key]<v[h[t/2]])
      {x=h[t];
      h[t]=h[t/2];
      h[t/2]=x;
      y=poz[h[t]];
      poz[h[t]]=poz[h[t/2]];
      poz[h[t/2]]=y;
      t/=2;}}

void del(long h[N],long *n,long k,long poz[N],long v[N])
{long key,son,aux,x,y,z,t;
t=h[k];
h[k]=h[(*n)];
h[(*n)]=t;
z=poz[h[(*n)]];
poz[h[(*n)--]]=poz[h[k]];
poz[h[k]]=z;
if(k>1&&v[h[k]]<v[h[k/2]])
      {key=h[k];
      x=poz[h[k/2]];
      y=poz[h[k]];
      while(k>1&&v[key]<v[h[k/2]])
            {t=poz[h[k]];
            poz[h[k]]=poz[h[k/2]];
            poz[h[k/2]]=t;
            z=h[k];
            h[k]=h[k/2];
            h[k/2]=z;
            k/=2;}}
else
      {do
            {son=0;
            if(2*k<=(*n))
                    {son=2*k;
                    if(2*k+1<=(*n)&&v[h[2*k+1]]<v[h[2*k]])
                            son=2*k+1;
                    if(v[h[son]]>=v[h[k]])
                            son=0;}
            if(son)
                    {aux=h[k];
                    h[k]=h[son];
                    h[son]=aux;
                    t=poz[h[son]];
                    poz[h[son]]=poz[h[k]];
                    poz[h[k]]=t;
                    k=son;}}
      while(son);}}
      
void push(list &q,long x,long y)
{Nod *p=new Nod;
p->info=x;
p->cost=y;
p->urm=q;
q=p;}

void modific(long h[N],long n,long d[N],long poz[N],long l,long k)
{long i,x,y,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;
            y=poz[h[i]];
            poz[h[i]]=poz[h[i/2]];
            poz[h[i/2]]=y;
            i/=2;}}}

int main()
{freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%ld%ld\n",&n,&m);
for(j=0;j<n;j++)
      g[j]=NULL;
for(i=1;i<=m;i++)
      {scanf("%ld%ld%ld\n",&a,&b,&c);
      a--;
      b--;
      push(g[a],b,c);
      push(g[b],a,c);}
for(k=0;k<n;k++)
      {d[k]=INF;
      par[k]=-1;
      l[k]=0;}
d[0]=0;
j=0;
for(i=0;i<n;i++)
      add(h,&j,poz,d,i);
while(j!=0)
      {i=h[1];
      l[i]=1;
      del(h,&j,poz[i],poz,d);
      for(p=g[i];p!=NULL;p=p->urm)
      if(l[p->info]==0&&p->cost<d[p->info])
             {d[p->info]=p->cost;
             par[p->info]=i;
             modific(h,j,d,poz,poz[p->info],d[p->info]);}}
k=0;
for(i=0;i<n;i++)
if(par[i]!=-1)
      {e+=d[i];
      k++;}
printf("%ld\n%ld\n",e,k);
for(j=0;j<n;j++)
if(par[j]!=-1)
      printf("%ld %ld\n",j+1,par[j]+1);
fclose(stdin);
fclose(stdout);
return 0;}