#include <bits/stdc++.h>

using namespace std;

#define int long long

struct muchie{
    int a, b, c;

    bool operator<(const muchie& alta) const{
        return c<alta.c;
    }
};

const int nmax=200005;
vector<muchie> m;
vector<muchie> r;
int tata[nmax];
int dim[nmax];
int n, M;
long long s;

int radacina(int x){
    if (tata[x]==x) return x;
    return tata[x]=radacina(tata[x]);
}

void unire(int x, int y){
    int rx = radacina(x);
    int ry = radacina(y);

    if (rx!=ry){
        if (dim[x]<dim[y]){
            tata[rx] = ry;
            dim[ry] += dim[rx];
        }
        else{
            tata[ry] = rx;
            dim[rx] += dim[ry];
        }
    }
}

void citire(){
    cin>>n>>M;

    muchie aux;
    for (int i=1; i<=M; ++i){
        cin>>aux.a>>aux.b>>aux.c;
        m.push_back(aux);
    }

    for(int i=1; i<=M; ++i){
        tata[i]=i;
        dim[i]=1;
    }

    sort(m.begin(), m.end());
}

void kruskal(){
    int num;
    muchie aux;

    for (auto& nod : m){
        if(radacina(nod.a) != radacina(nod.b)){
            unire(nod.a, nod.b);
            aux.a=nod.a; aux.b=nod.b;
            r.push_back(aux);
            s+=nod.c;
            ++num;
            if(num == n-1) return;
        }
    }
}

void afisare(){
    cout<<s<<"\n"<<n-1<<"\n";

    for(auto& aux : r){
        cout<<aux.a<<" "<<aux.b<<"\n";
    }
}

signed main (){

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie();

    citire();

    kruskal();

    afisare();

    return 0;
}