#include <iostream>
#include <fstream>
#include <vector>
#define nmax 200001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie {
    int x,y,c;
}e[2*nmax];
vector <int> a[nmax];
int n,m,C[nmax],Ansx[nmax],Ansy[nmax];
void citire() {
    f>>n>>m;
    for (int i=1;i<=m;i++) {
        f>>e[i].x>>e[i].y>>e[i].c;
    }
}
void QS(int left,int right) {
    int i=left;
    int j=right;
    muchie aux;
    int pivot=e[(i+j)/2].c;
    while (i<=j) {
        while (e[i].c<pivot) {
            i++;
        }
        while (pivot<e[j].c) {
            j--;
        }
        if (i<=j) {
            aux=e[i];
            e[i]=e[j];
            e[j]=aux;
            i++;
            j--;
        }
    }
    if (i<right) QS(i,right);
    if (j>left) QS(left,j);
}
void rez() {
    QS(1,m);
    for (int i=1;i<=n;i++) {
        C[i]=i;
    }
    long long int Cost=0;
    int Nrmuchii=0;
    for (int i=1;Nrmuchii<n-1;i++) {
        //cout<<Nrmuchii<<"\n";
        if (C[e[i].x]!=C[e[i].y] ) {
            Ansx[++Nrmuchii]=e[i].x;
            Ansy[Nrmuchii]=e[i].y;
            int p1=e[i].x;
            int p2=e[i].y;
            Cost=Cost+e[i].c;
            if (C[p1]<C[p2]) {
                C[p2]=C[p1];
                a[p1].push_back(p2);
                for (int j=0;j<a[p2].size();j++) {
                    int p=a[p2][j];
                    C[p]=C[p1];
                    a[p1].push_back(p);
                }
            }
            else {
                C[p1]=C[p2];
                a[p2].push_back(p1);
                for (int j=0;j<a[p1].size();j++) {
                    int p=a[p1][j];
                    a[p2].push_back(p);
                    C[p]=C[p2];
                }
            }
        }
    }
    /*
    for (int i=1;i<=n;i++) {
        cout<<C[i]<<" ";
    }
    */
    g<<Cost<<"\n";
    g<<Nrmuchii<<"\n";
    for (int i=1;i<=Nrmuchii;i++) {
        g<<Ansx[i]<<" "<<Ansy[i]<<"\n";
    }

}
int main() {
    citire();
    rez();
    return 0;
}