#include <fstream>
#include <vector>
#include <algorithm>
#define DMAX 400011
using namespace std;
int n,m,s;
int x[DMAX],y[DMAX],c[DMAX],gr[DMAX],ind[DMAX];
vector <int> sol;
bool cmp(int i, int j){
     return (c[i]<c[j]);
}
int grupa(int x){
    int r,y;
    for(r=x;r!=gr[r];r=gr[r]);
    for(;x!=gr[x];){
        y=gr[x];
        gr[x]=r;
        x=y;            
    }
    return r;
}
void uneste(int x, int y){
     gr[grupa(x)]=grupa(y);
}
int main(){
    int i;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(i=1;i<=m;i++){
     f>>x[i]>>y[i]>>c[i];
     ind[i]=i;
    }
    for(i=1;i<=n;i++) gr[i]=i;
    sort(ind+1,ind+m+1,cmp);
    for(i=1;i<=m;i++){
     if(grupa(x[ind[i]])!=grupa(y[ind[i]])){
      s+=c[ind[i]];
      uneste(x[ind[i]],y[ind[i]]);
      sol.push_back(ind[i]); 
     }
    }
    g<<s<<"\n"<<n-1<<"\n";
    for(i=0;i<n-1;i++)
     g<<x[sol[i]]<<" "<<y[sol[i]]<<"\n";
    return 0;
}