#include <stdio.h>
#define INF 10000
#define MAXN 200000
#define MAXM 400000
FILE *fin, *fout;

int k=1,v[MAXN+1],l[2*MAXN+1],next[2*MAXN+1],w[2*MAXN+1];
int d,h[MAXN+1],key[MAXN+1],e[MAXN+1],poz[MAXN+1];
bool viz[MAXN+1];

struct edge{
  int x,y;
}sol[MAXM];

void downheap(int nod){
  int son=nod*2+1,aux;
  if(son+1<d && key[h[son+1]]<key[h[son]])
    son++;
  while(son<d && key[h[nod]]>key[h[son]]){
    aux=h[nod];
    h[nod]=h[son];
    h[son]=aux;
    poz[h[nod]]=nod;
    poz[h[son]]=son;
    nod=son;
    son=nod*2+1;
    if(son+1<d && key[h[son+1]]<key[h[son]])
      son++;
  }
}

void upheap(int nod){
    int parent=(nod-1)/2,aux;
    while(parent>=0 && key[h[nod]]<key[h[parent]]){
        aux=h[nod];
        h[nod]=h[parent];
        h[parent]=aux;
        poz[h[nod]]=nod;
        poz[h[parent]]=parent;
        nod=parent;
        parent=(nod-1)/2;
    }
}

void heapify(){
  int i;
  for(i=(d-1)/2; i>=0; i--)
    downheap(i);
}

void vecini(int nod){
  int i=v[nod];
  while(l[i]){
    if(!viz[l[i]] && w[i]<key[l[i]]){
      key[l[i]]=w[i];
      e[l[i]]=nod;
      upheap(poz[l[i]]);
    }
    i=next[i];
  }
}

int main(){
  FILE *fin=fopen("apm.in","r");
  FILE *fout=fopen("apm.out","w");
  int n,m,i,apm=0,mapm=0,x,y,c;

  fscanf(fin,"%d%d",&n,&m);
  for(i=0; i<m; i++){
    fscanf(fin,"%d%d%d",&x,&y,&c);
    l[k]=y; w[k]=c; next[k]=v[x]; v[x]=k++;
    l[k]=x; w[k]=c; next[k]=v[y]; v[y]=k++;
  }
  for(i=1; i<=n; i++){
    h[i-1]=i;
    poz[i]=i-1;
    key[i]=INF;
  }
  key[1]=0;
  viz[1]=1;
  d=n;
  heapify();
  while(d){
    int nod=h[0];
    apm+=key[nod];
    sol[mapm].x=nod;
    sol[mapm++].y=e[nod];
    h[0]=h[--d];
    downheap(0);
    viz[nod]=1;
    vecini(nod);
  }
  fprintf(fout,"%d\n%d\n",apm,mapm-1);
  for(i=1; i<mapm; i++)
    fprintf(fout,"%d %d\n",sol[i].x,sol[i].y);
  fclose(fin);
  fclose(fout);
  return 0;
}