#include <iostream>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define LE 500666
#define mp make_pair
#include <algorithm>

struct trei {
    int x,y,z;
} X[LE];
pair<int,int> edge[LE];
int result,n,m,i,K,root[LE];
int height[LE];

int  get_root(int nod) {
    while (nod!=root[nod]) nod=root[nod];
    return nod;
}

void unite(int nod1,int nod2) {
    int root1=get_root(nod1),root2=get_root(nod2);

    if (height[root1]==height[root2]) {
        root[root1]=root2,height[root2]++;
        return;
    }
    if (height[root1]>height[root2]) {
        root[root2]=root1;
        return;
    }
    root[root1]=root2;
}

bool comp(trei i1,trei i2) {
    return i1.z<i2.z;
}

int main() {
    f>>n>>m;
    for(i=1; i<=m; ++i) f>>X[i].x>>X[i].y>>X[i].z;
    sort(X+1,X+m+1,comp);
    for(i=1; i<=n; ++i) root[i]=i;

    for(i=1; i<=m; ++i) {
        if (get_root(X[i].x)==get_root(X[i].y)) continue;
        unite(X[i].x,X[i].y);
        result+=X[i].z;
        edge[++K]=mp(X[i].x,X[i].y);
    }

    g<<result<<'\n';

    g<<n-1<<'\n';

    for(i=1; i<=K; ++i)
        g<<edge[i].first<<" "<<edge[i].second<<'\n';


    f.close();
    g.close();
    return 0;
}