#include <iostream>
#include <fstream>
#include <algorithm>
#define mod 10000
#define x first
#define y second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int t[100001],n,m,i,tip,rx,ry,x,y,j,cost;
pair <int,int> sol[200001];
int k;
pair <int ,pair<int,int>>a[400001];
int rad(int x){
while(t[x]>0){
    x=t[x];
}
return x;

}
int main()
{
  fin>>n>>m;
  for(i=1;i<=n;i++)
    t[i]=-1;
for(j=1;j<=m;j++){
    fin>>a[j].y.x>>a[j].y.y>>a[j].x;
}
sort(a+1,a+m+1);
for(j=1;j<=m;j++){
      int   xx=a[j].y.x;
       int  yy=a[j].y.y;
    rx=rad(xx);
    ry=rad(yy);
    if(rx==ry){
       continue;
    }
  else{
    cost+=a[j].x;
    sol[++k].x=xx;
    sol[k].y=yy;
    if(t[rx]<t[ry]){
        t[rx]+=t[ry];
        t[ry]=rx;
    }
    else{
        t[ry]+=t[rx];
        t[rx]=ry;
    }
  }
}
fout<<cost<<"\n"<<k<<"\n";
for(i=1;i<=k;i++)
    fout<<sol[i].x<<" "<<sol[i].y<<"\n";
}