/*https://www.pbinfo.ro/articole/6024/paduri-de-multimi-disjuncte*/ //pt subpr de Radacina si Concatenare

#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define DIM 200005

using namespace std;

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

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

int n, m, T[DIM], rang[DIM]; // T - vectorul de tati; rang - rangul fiecarui vf(adancimea)

int Radacina(int ind){
    if(T[ind] == ind)
        return ind;
    else{
        T[ind] = Radacina(T[ind]);
        return T[ind];
    }
}

void Concatenare(int rx, int ry){
    if(rx != ry){
        if(rang[rx] > rang[ry])
            T[ry] = rx;
        else{
            T[rx] = ry;
            if(rang[ry] == rang[rx])
                rang[ry]++;
        }
    }
}

bool compara(muchie e1, muchie e2){
    return e1.c < e2.c;
}

int main()
{
    f>>n>>m;
    int contor = 0; //numara cate muchii sunt in apm
    for(int i=1; i<=n; i++){
        T[i] = i;
        rang[i] = 1;
    }
    vector <muchie> v;
    vector <muchie> folosit;
    muchie l;
    for(int i=1; i<=m; i++){
        f>>l.x>>l.y>>l.c;
        v.push_back(l);
    }
    int cmin = 0;
    sort(v.begin(), v.end(), compara);
    for(int i=0; i<m; i++){
        int rx = Radacina(v[i].x), ry = Radacina(v[i].y); //rx, ry = reprezentantii nodurilor x, respectiv y
        if(rx != ry){
            cmin += v[i].c;
            folosit.push_back(v[i]);
            contor++;
            Concatenare(rx,ry);
        }
    }
    g<<cmin<<"\n"<<contor<<"\n";
    for(int i=0; i<contor; i++)
        g<<v[i].y<<" "<<v[i].x<<"\n";
}