#include <iostream>
#include <fstream>
using namespace std;

struct muchie {
    int c1;
    int c2;
    int cost;
    bool sel;
};

muchie muchii[400000];

int divide(int st, int dr) {
    int wall=st-1;
    for(int i=st;i<dr;i++) {
        if(muchii[i].cost<muchii[dr].cost) {
            wall++;
            swap(muchii[i],muchii[wall]);
        }
        else if(muchii[i].cost==muchii[dr].cost&&muchii[i].c1<muchii[dr].c1) {
            wall++;
            swap(muchii[i],muchii[wall]);
        }
    }
    swap(muchii[wall+1],muchii[dr]);
    return wall+1;
}

void quick_sort(int st, int dr) {
    if(st<dr) {
        int pivot=divide(st,dr);
        quick_sort(st,pivot-1);
        quick_sort(pivot+1,dr);
    }
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n,m;
    fin>>n>>m;
    for(int i=0;i<m;i++)
        fin>>muchii[i].c1>>muchii[i].c2>>muchii[i].cost;
    quick_sort(0,m-1);
    int cc[200000];
    for(int i=1;i<=n;i++)
        cc[i]=i;
    int cost=0,nMuchii=0,k=0,maxim,minim;
    while(nMuchii<n-1) {
        if(cc[muchii[k].c1]!=cc[muchii[k].c2]) {
            muchii[k].sel=true;
            maxim=max(cc[muchii[k].c1],cc[muchii[k].c2]);
            minim=min(cc[muchii[k].c1],cc[muchii[k].c2]);
            cost+=muchii[k].cost;
            for(int j=1;j<=n;j++)
                if(cc[j]==maxim)
                    cc[j]=minim;
            nMuchii++;
        }
        k++;
    }
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(int i=0;i<m;i++)
        if(muchii[i].sel)
            fout<<muchii[i].c1<<" "<<muchii[i].c2<<'\n';
    return 0;
}