//KRUSKAL
#include <bitset>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX=200001;
const int MMAX=400001;

struct muc
{
     int x,y;
     short int c;
}v[MMAX];
int n,m,t[NMAX];

bitset <MMAX> b=0;


int partitionare(int st,int dr)
{
     int i=st+1, j=dr;
     short int x=v[st].c;

     while(i<=j)
     {
          if(v[i].c<=x)  i++;

          if(v[j].c>x)  j--;

          if(i<j && v[i].c>x && v[j].c<=x)
               swap(v[i],v[j]), i++, j--;
     }

     swap(v[st],v[j]);
     return j;
}

void qsort(int st,int dr)
{
     if(st>=dr) return;

     int mij=partitionare(st,dr);
     qsort(st,mij-1);
     qsort(mij+1,dr);
}

int radacina(int x)
{
     if(t[x]==0)
          return x;


     int rad=radacina(t[x]);
     t[x]=rad;
     return rad;
}

long long cost;
int main()
{
     fin>>n>>m;
     for(int i=1;i<=m;i++)
          fin>>v[i].x>>v[i].y>>v[i].c;

     qsort(1,m);
     //for(int i=1;i<=m;i++)
          //fout<<v[i].c<<' ';

     int cnt=0;
     for(int i=1 ;i<=m, cnt<n-1; i++)
     {
          int r1,r2;
          r1=radacina(v[i].x);
          r2=radacina(v[i].y);

          if(r1!=r2)
          {
               t[r1]=r2;
               cnt++;
               cost+=(long long)v[i].c;
               b[i]=true;
          }
     }

     fout<<cost<<'\n'<<cnt<<'\n';
     for(int i=1;i<=m, cnt;i++)
     {
          if(b[i]==true){
               fout<<v[i].x<<' '<<v[i].y<<'\n';
               cnt--;
          }
     }
    return 0;
}