#include <bits/stdc++.h>

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

const int NMax = 200003;

struct muchie{
    int x,y,c;
};

muchie M[NMax];
int x,n,m,y,p,vf1,vf2,S;
int rang[NMax],root[NMax];
vector<pair<int,int> > ans;

int rad(int x){
    while(x != root[x])
        x = root[x];
    return x;
}
bool cmp(muchie x, muchie y){
    return (x.c < y.c);
}
int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; ++i){
        f >> M[i].x >> M[i].y >> M[i].c;
    }
    sort(M + 1, M + 1 + m, cmp);
    for(int i = 1; i <= n; ++i){
        rang[i] = 1;
        root[i] = i;
    }
    for(int i = 1; i <= m && ans.size() < n - 1; ++i){
        vf1 = rad(M[i].x);
        vf2 = rad(M[i].y);

        if(vf1 != vf2){
            S += M[i].c;
            ans.push_back(make_pair(M[i].x,M[i].y));
            if(rang[vf1] > rang[vf2]){
                rang[vf1] += rang[vf2];
                root[vf2] = vf1;
            }else{
                rang[vf2] += rang[vf1];
                root[vf1] = vf2;
            }
        }
    }
    g << S << '\n';
    g << ans.size() << '\n';
    for(int i = 0;i < ans.size(); ++i){
        g << ans[i].first << ' ' << ans[i].second << '\n';
    }
    return 0;
}