#include <fstream>
#include <algorithm>
#define NMAX 400200
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,i,CM=0,M=0;
int X[NMAX],Y[NMAX],C[NMAX],GR[NMAX],I[NMAX],V[NMAX],RG[NMAX];

bool comp(int a,int b) {
    return(C[a]<C[b]);
}
int rad(int x) {
    int p,y;
    for (p=x;p!=GR[p];p=GR[p]);
    for (;x!=GR[x];) {
        y=GR[x];
        GR[y]=p;
        x=y;
    }
    return p;
}
void unite(int x,int y) {
    if (RG[x]>=RG[y]) GR[y]=x;
                 else GR[x]=y;
    if (RG[x]==RG[y]) RG[x]++;
}

int main() {
    f >> n >> m;
    for (i=1;i<=m;i++) {
        f >> X[i] >> Y[i] >> C[i];
        I[i]=i;
    }
    for (i=1;i<=n;i++) GR[i]=i,RG[i]=1;
    sort(I+1,I+m+1,comp);
    for (i=1;i<=m;i++)
        if(rad(X[I[i]])!=rad(Y[I[i]])) {
            CM+=C[I[i]];
            V[++M]=I[i];
            unite(rad(X[I[i]]),rad(Y[I[i]]));
        }
    g << CM << '\n';
    g << M << '\n';
    for (i=1;i<=M;i++)
        g << X[V[i]] << ' ' << Y[V[i]] << '\n';
    f.close();g.close();
    return 0;
}