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

int n, m, i, j, x, y, t[200002], k, rx, ry, cost;
pair< int, pair<int, int> >v[400002];
pair< int, int >sol[200002];

/// Luam mereu cea mai mica muchie ca cost si verificam daca capetele sunt sau nu din aceasi componenta comparand radacinile
/// Trebuie sa avem n-1 muchii deoarece construim un arbore

int radacina(int nod){
    while(t[nod]>0){
        nod=t[nod];
    }
    int r=nod;
    while(t[nod]>0){
        int aux=t[nod];
        t[nod]=r;
        nod=aux;
    }
    return r;
}

int main(){
    fin>>n>>m;
    for(i=1; i<=n; i++){
        t[i]=-1;
    }
    for(i=1; i<=m; i++){
        fin>>v[i].second.first>>v[i].second.second>>v[i].first;
    }
    sort(v+1, v+m+1);
    /// in k tinem numarul de muchii utilizate
    for(i=1; i<=m; i++){
        x=v[i].second.first;
        y=v[i].second.second;
        rx=radacina(x);
        ry=radacina(y);
        if(rx!=ry){
            /// le lipim si le adaugam la solutie
            k++;
            cost+=v[i].first;
            sol[k].first=x;
            sol[k].second=y;
            if(t[rx]<t[ry]){
                t[rx]+=t[ry];
                t[ry]=rx;
            }else{
                t[ry]+=t[rx];
                t[rx]=ry;
            }
            if(k==n-1){
                break;
            }
        }
    }
    fout<<cost<<"\n";
    fout<<k<<"\n";
    for(i=1; i<=k; i++){
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
    }
}