#include <fstream>
#include <algorithm>
#include <string.h>

#define max_n 200000
#define max_m 400000

using namespace std;

int n,m,i,j,x1,y1,c1,cost,rez,k,nr,q;
typedef struct costuri{
    int x,y,c;
};
costuri muchie[max_m];
int T[max_n],rang[max_n];
bool ok[max_n];
int sol[max_m][2];

inline bool cmp(const costuri &a,const costuri &b) {
    return a.c<b.c;
}

inline int multime(int nod) {
    if (T[nod]!=nod)
        T[nod]=multime(T[nod]);
    return T[nod];
}

void reuneste(int i,int j) {
    i=multime(i);
    j=multime(j);
    if (i==j) return;
    if (rang[i]<rang[j])
        T[i]=j;
    else
        T[j]=i;
    if (rang[i]==rang[j])
        rang[i]++;
}

int main () {
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for (i=1; i<=m; i++) {
        f>>x1>>y1>>c1;
        muchie[i].c=c1;
        muchie[i].x=x1;
        muchie[i].y=y1;
    }

    sort(muchie+1,muchie+m+1,cmp);

    for (i=1; i<=n; i++) {
        T[i]=i;
        rang[i]=0;
    }

    memset(ok,false,sizeof(ok));
    q=0;
    for (k=1; k<=m; k++) {
        i=muchie[k].x;
        j=muchie[k].y;
        cost=muchie[k].c;
        if (multime(i)!=multime(j)) {
            reuneste(i,j);
            rez+=cost;
            q++;
            sol[q][0]=i;
            sol[q][1]=j;
        }
    }
    g<<rez<<'\n';
    g<<q<<'\n';
    for (i=1; i<=q; i++)
        {g<<sol[i][0]<<" "<<sol[i][1];
         g<<'\n';
        }
    return 0;
}