#include <bits/stdc++.h>
#define MMAX 400009
#define NMAX 200009
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{int x; int y; int c;};
muchie muc[MMAX];
bool compar(muchie a, muchie b)
{
  return a.c<b.c;
}
int n,m;
int urs[NMAX];
int tata[NMAX],h[NMAX];
void citire();
void Union(int x,int y);
int Find(int x);
int main()
{
   citire();
    return 0;
}
void citire()
{int i;
 int a,b,ca,cb;
 fin>>n>>m;
 for(i=1;i<=m;i++)
    {
     fin>>muc[i].x>>muc[i].y>>muc[i].c;
    }
  sort(muc+1,muc+m+1,compar);
  int nrc=0,cost=0;
  for(i=1;i<=m && nrc!=n-1;i++)
    {
      a=muc[i].x;b=muc[i].y;
      ca=Find(a);
      cb=Find(b);
      if(cb!=ca)
        Union(ca,cb),nrc++,cost+=muc[i].c,urs[nrc]=i;

    }
 fout<<cost<<'\n'<<nrc<<'\n';
 for(i=1;i<n;i++)
    fout<<  muc[urs[i]].x<<" "<<muc[urs[i]].y<<"\n";
}

int Find(int x)
{
    int rad=x;int aux;
    while(tata[rad])
        rad=tata[rad];
    while(tata[x])
    {   aux=tata[x];
        tata[x]=rad;
        x=aux;
    }
    return rad;
}
void Union(int x,int y)
{   if(h[x]<h[y])
    tata[x]=y;
    else
    {tata[y]=x;if(h[x]==h[y])h[x]++;}
}