/*
ARBORE PARTIAL DE COST MINIM

Se da un graf conex neorientat G cu N noduri si M muchii, fiecare muchie avand
asociat un cost. Se cere sa se determine un subgraf care cuprinde toate nodurile
si o parte din muchii, astfel incat subgraful determinat sa aiba structura de
arbore si suma costurilor muchiilor care il formeaza sa fie minim posibila.
*/

#include <stdio.h>
#include <algorithm>
#define Nmax 200005
#define Mmax 400005
using namespace std;
struct much{int x,y,c;}a[Mmax];
int t[Nmax],ind[Nmax];

int cmp(const much a, const much b){
  return (a.c < b.c);
}

int down(int x){
  int a=x,p;
  while (t[a]!=a) a=t[a];
  while (t[x]!=x){p=t[x];t[x]=a;x=p;}
return a;
}
int check(int x,int y){ return (down(x)==down(y)); }
void join(int x,int y){ t[t[y]]=t[t[x]]; }

int main(){
  freopen("apm.in","r",stdin); freopen("apm.out","w",stdout);
  long n,m,i,k,sol=0;
  
  scanf("%d %d",&n,&m);
  for (i=1;i<=m;++i) scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
  for (i=1;i<=n;++i)t[i]=i;

  sort(a+1,a+m+1,cmp);

  for (i=1,k=1; i<=m && k<=n; ++i)
    if (check(a[i].x, a[i].y)==0){
      join(a[i].x, a[i].y);
      sol+=a[i].c;
      ind[k++]=i;
    }
  
  printf("%d\n%d\n",sol,n-1);
  for (i=1;i<n;++i)
    printf("%d %d\n",a[ind[i]].x,a[ind[i]].y);

return 0;
}