#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
const int NmaxVf = 200005, NmaxMuchii = 400005;

struct Muchie {
    int v1, v2, cost;
};
Muchie G[NmaxMuchii];
int A[NmaxVf], C[NmaxVf], n, m;

void Read() {
    fin>>n>>m;
    for (int i=1; i<=m; i++){
        fin>>G[i].v1>>G[i].v2>>G[i].cost;
        C[i]=i;
    }
}

void SortareMuchii(int st, int dr) {
    Muchie x;
    int i, j;
    if(st<dr) {
        x=G[st], i=st, j=dr;
        while (i<j) {
            while (i<j&&G[j].cost>=x.cost) j--;
            G[i]=G[j];
            while(i<j&&G[i].cost<=x.cost) i++;
            G[j]=G[i];
        }
        G[i]=x;
        SortareMuchii(st, i-1);
        SortareMuchii(i+1, dr);
    }
}

void Afisare() {
    int costAPM=0;
    for(int i=1; i<n; i++) costAPM+=G[A[i]].cost;
    fout<<costAPM<<endl;
    fout<<n-1<<endl;
    for(int i=1; i<n; i++) {
        fout<<G[A[i]].v1<<' '<<G[A[i]].v2<<endl;
    }
}
int main()
{
    int minim, maxim, NrMSel=0;
    Read();
    SortareMuchii(1, m);
    for(int i=1; NrMSel<n-1; i++) {
        if(C[G[i].v1]!=C[G[i].v2]) {
            A[++NrMSel]=i;
            if(C[G[i].v1]<C[G[i].v2]) {
                minim=C[G[i].v1];
                maxim=C[G[i].v2];
            } else {
                minim=C[G[i].v2];
                maxim=C[G[i].v1];
            }
            for(int j=1; j<=n; j++)
                if(C[j]==maxim) C[j]=minim;
        }
    }
    Afisare();
    return 0;
}