#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, x, y, z, k, s;

struct el{
    int x,y,cost;
};

vector<pair<int, int>> v;
vector<el> muchii;
bool vizitat[200001];
int tt[200001];

bool cmp(el a, el b) {
    return a.cost < b.cost;
}

int comp(int x){
    int y=x;
    while(y!=tt[y]){
        y=tt[y];
    }
    int xx=x;
    while(xx!=y){
        int next=tt[xx];
        tt[xx]=y;
        xx=next;
    }
    return y;
}

void unire(int x, int y){
    int xx=comp(x);
    int yy=comp(y);
    tt[xx]=yy;
}

int main() {
    fin >> n >> m;
    for(int i=1;i<=n;i++){
        tt[i]=i;
    }
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> z;
        el nr;
        nr.x=x;
        nr.y=y;
        nr.cost=z;
        muchii.push_back(nr);
    }
    sort(muchii.begin(), muchii.end(), cmp);

    for(auto a:muchii){
        int xx=a.x;
        int yy=a.y;
        int zz=a.cost;
        if(comp(xx)!=comp(yy)){
            unire(xx,yy);
            s+=zz;
            v.push_back({xx,yy});
        }
    }

    fout << s << '\n';
    fout<<v.size()<<'\n';
    for (auto u : v) {
        fout << u.first << " " << u.second << '\n';
    }
    return 0;
}