#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n,m,cnt,total,ok;
int sefu[400002];
struct ura {
    int nods,nodf,cost;
} v[400002],valid[400002];


void Read() {
    ifstream f("apm.in");
    f>>n>>m;
    for(int i=1; i<=m; ++i)
        f>>v[i].nods>>v[i].nodf>>v[i].cost;
    f.close();
}

void Show() {
    ofstream g("apm.out");
    g<<total<<'\n';
    g<<cnt<<'\n';
    for(int i=1; i<=cnt; ++i)
        g<<valid[i].nods<<' '<<valid[i].nodf<<'\n';

}


void Check() {
    for(int i=1; i<=m; ++i)
        cout<<sefu[i]<<' ';
}

bool cmp(ura a,ura b) {
    return a.cost<b.cost;
}

int sef(int nod) {
    if(sefu[nod]==nod)
        return nod;
    return sefu[nod]=sef(sefu[nod]);
}

void Adauga(int nod1,int nod2, int pret) {
    int sef1,sef2;
    sef1=sef(nod1);
    sef2=sef(nod2);
    if(sef1!=sef2) {

        total+=pret;
        sefu[sef2]=sef1;
        valid[++cnt].nods=nod1;
        valid[cnt].nodf=nod2;


    }
}
void Solve() {
    for(int i=1; i<=n; ++i)
        sefu[i]=i;
    for(int i=1; i<=m && !ok; ++i) {
        if(cnt==n-1)
            ok=1;
        if(!ok)
            Adauga(v[i].nods,v[i].nodf,v[i].cost);

    }
    Show();
}

int main() {
    Read();
    sort(v+1,v+m+1,cmp);
    Solve();
    //Check();

}