#include<bits/stdc++.h>
#include <fstream>
#include <algorithm>
#include <vector>
#define N 200005
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,M;
int m[N],sz[N];

int nrmuchii,cost;

struct edge
{int a,b,c;
}e[400005];

void read()
{int i;
 fin>>n>>M;
 for(i=1;i<=M;++i)
    fin>>e[i].a>>e[i].b>>e[i].c;

}


bool comp(edge A,edge B)
{return A.c<B.c;}

int Find(int x)
{int root_x=x;
 while(m[root_x]!=root_x)
    root_x=m[root_x];
 int aux;
 while(x!=m[x])
 {aux=m[x];
  m[x]=root_x;
  x=aux;
 }
 return root_x;
}

void Union(int A,int B)
{int root_A=Find(A);
 int root_B=Find(B);

 if(sz[root_A]<sz[root_B])
 {sz[root_B]+=sz[root_A];
  m[root_A]=root_B;
 }
  else
  {sz[root_A]+=sz[root_B];
   m[root_B]=root_A;
  }
}


void solve()
{int i,x,y;

 vector< pair <int,int> >sol;

 sort(e+1,e+M+1,comp);

 for(i=1;i<=n;++i)
        m[i]=i,sz[i]=1;

  for(i=1;i<=M&&sol.size()<n-1;++i)
  {x=Find(e[i].a);
   y=Find(e[i].b);

   if(x!=y)
   {cost+=e[i].c;
    nrmuchii++;

    Union(x,y);

    sol.push_back(make_pair(e[i].a,e[i].b));
   }
  }
  fout<<cost<<"\n"<<nrmuchii<<"\n";
  for(i=0;i<sol.size();++i)
    fout<<sol[i].first<<" "<<sol[i].second<<"\n";

}

int main()
{
    int i;
    read();
    solve();




    return 0;
}