#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct Muchie{
    int x,y,c;
};
vector <int> C(200001); //C[i] componenta conexa din care face parte nodul i
vector < Muchie > V;
vector <Muchie> Sol;

int n,m,suma;
bool comp (const Muchie &a, const Muchie &b){
    return a.c<b.c;
}
void read(){
    f>>n>>m;
    int x,y,c;
    for(int i=0;i<m;i++){
        f>>x>>y>>c;
        Muchie m;
        m.x=x;
        m.y=y;
        m.c=c;
        V.push_back(m);
        C[x]=x;
        C[y]=y;
    }
    sort(V.begin(),V.end(),comp);//sortez  dupa cost
   /* for(vector<Muchie>::iterator it=V.begin();it!=V.end();it++){
        cout<<(*it).c<<endl;
    }*/
    for(int i=0;i<m;i++){
        if(C[V[i].x] != C[V[i].y]){
            suma+=V[i].c;
            Sol.push_back(V[i]);
            int minim=min(C[V[i].x],C[V[i].y]);
            int maxim=max(C[V[i].x],C[V[i].y]);
            replace(C.begin(),C.end(),maxim,minim);
        }
    }
    g<<suma<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;i++){
        g<<Sol[i].y<<" "<<Sol[i].x<<"\n";
    }
}
int main()
{
    read();
    return 0;
}