#include <fstream>
#include <algorithm>
using namespace std;
pair<long long,pair<long long,long long> > c[400010];
pair<long long,long long> sol[400010];
long long t[400010];
long long i,n,m,u;
long long x,y,rx,ry,cost;

long long aflareRadacina (long long x) {
    while (t[x]>0) {
        x=t[x];
    }
    return x;
}

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>c[i].second.first>>c[i].second.second;
        fin>>c[i].first;
    }
    sort (c+1,c+m+1);
    for (i=1;i<=n;i++) {
        t[i]=-1;
    }
    for (i=1;i<=m;i++) {
        x=c[i].second.first;
        y=c[i].second.second;
        rx=aflareRadacina(x);
        ry=aflareRadacina(y);
        if (rx!=ry) {
            if (t[rx]<t[ry]) {
                t[rx]+=t[ry];
                t[y]=x;
                sol[++u]=make_pair(x,y);
            }
            else {
                t[ry]+=t[rx];
                t[x]=y;
                sol[++u]=make_pair(x,y);
            }
            cost+=c[i].first;
        }
    }
    fout<<cost<<"\n"<<u<<"\n";
    for (i=1;i<=u;i++) {
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
    }
    return 0;
}