/*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{
        int x = Radacina(T[ind]);
        T[ind] = x;
        return x;
    }
}

void Concatenare(int k, int p){
    int rk = Radacina(k), rp = Radacina(p);
    if(rk != rp){
        if(rang[rk] > rang[rp])
            T[rp] = rk;
        else{
            T[rk] = rp;
            if(rang[rp] == rang[rk])
                rang[rp] ++;
        }
    }
}

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;
    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++)
        if(T[v[i].x] != T[v[i].y]){
            cmin += v[i].c;
            folosit.push_back(v[i]);
            contor++;
            Concatenare(v[i].x,v[i].y);
        }
    g<<cmin<<"\n"<<contor<<"\n";
    for(int i=0; i<contor; i++)
        g<<v[i].y<<" "<<v[i].x<<"\n";
}