#include<iostream>
#include<fstream>
#include<list>
using namespace std;
int n, m, cc[200002];
struct muchie{
    int a, b, c;
};
list<muchie> muchii, muchii_alese;
muchie mm(int a, int b, int c){
    muchie m;
    m.a=a; m.b=b; m.c=c;
    return m;
}
bool cmp(muchie m1, muchie m2){
    return m1.c<m2.c;
}
void read(){
    ifstream f("apm.in");
    f>>n>>m;
    int a, b, c;
    for(int i=0;i<m;i++)
    {
        f>>a>>b>>c;
        muchii.push_back(mm(a, b, c));
    }
    for(int i=1;i<=n;i++)
        cc[i]=i;
    muchii.sort(cmp);
    return;
    for(list<muchie>::iterator it=muchii.begin(); it!=muchii.end(); it++){
        cout<<it->a<<" "<<it->b<<" "<<it->c<<"\n";
    }
}
int c=0, min1, max1, cost;
int main(){
    read();
    muchie m2;
    while(muchii.size()){
        m2=muchii.front(); muchii.pop_front();
        if(cc[m2.a]!=cc[m2.b]){
            min1=min(cc[m2.a], cc[m2.b]);
            max1=max(cc[m2.a], cc[m2.b]);
            for(int i=1;i<=n;i++)
                if(cc[i]==max1) cc[i]=min1;
            c++;
            cost+=m2.c;
            muchii_alese.push_back(m2);
        }
        if(c==n-1) break;
    }
    ofstream g("apm.out");
    g<<cost<<"\n"<<c<<"\n";
    while(muchii_alese.size())
        g<<muchii_alese.front().a<<" "<<muchii_alese.front().b<<"\n", muchii_alese.pop_front();
    return 0;
}