#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n,m,costfinal,nr1,r[200005],nr[200002];

struct carnat{
int x,y,cost;
}q[200002],rez[200002];

void read(){
  f>>n>>m;
  for(int i=1;i<=m;i++) f>>q[i].x>>q[i].y>>q[i].cost;
}

bool cmp(carnat a, carnat b)
{
    return a.cost<b.cost;
}

int root(int x){
if(r[x]==x) return x;
return root(r[x]);
}

void solve(){
   int n1,n2;
  sort(q+1,q+m+1,cmp);
  for(int i=1;i<=n;i++)
  {
      r[i]=i;
      nr[i]=1;
  }
  for(int i=1;i<=m;i++)
  {
      n1=root(q[i].x);
      n2=root(q[i].y);
      if(n1==n2) continue;
        if(nr[n1]>=nr[n2])
        {
            nr[n1]=+nr[n2];
            r[n2]=n1;
        }
        else
        {
            nr[n2]=+nr[n1];
            r[n1]=n2;
        }
        costfinal+=q[i].cost;
        nr1++;
        rez[nr1]=q[i];

  }
}

void write(){
  g<<costfinal<<"\n"<<nr1<<"\n";
  for(int i=1;i<=nr1;i++)
  {
      g<<rez[i].y<<" "<<rez[i].x<<"\n";
  }
}

int main(){

  read();
  solve();
  write();

  return 0;
}