#include <fstream>
#include <algorithm>
#define NM 400009
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,i,j,s;
int gr[NM];
vector < int > rsp;
struct apm{
   int x,y,c;
};
apm a[NM];
bool cmp(apm t, apm l){
  return t.c<l.c;
}
int grupa(int i){
  if(gr[i]==0) return i;
  gr[i]=grupa(gr[i]);
  return gr[i];
}
void unire(int i,int j){
  gr[grupa(i)]=grupa(j);
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++) f>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=m;i++){
        if(grupa(a[i].x)!=grupa(a[i].y)){
            s+=a[i].c; unire(a[i].x,a[i].y);
            rsp.push_back(i);
        }
    }
    g<<s<<'\n';
    g<<n-1<<'\n';
    for(i=0;i<rsp.size();i++)
        g<<a[rsp[i]].x<<' '<<a[rsp[i]].y<<'\n';
    return 0;
}