/**
    * code by purplecoder
*/
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

const int MAXN = 2e5 + 1, MAXM = 4e5 + 1;
int tata[MAXN], n, m, ans;

struct muchie{
    int u; //nod
    int v; //nod
    int w; //cost
    int ok; //daca pastram muchia este 1, daca nu 0
}muc[MAXM];

bool cmp(muchie a, muchie b){
    return a.w < b.w;
}

int find_tata(int x){
    int cop = x;
    while(tata[x] != x){
        x = tata[x];
    }
    while(cop != x){
        int tmp = tata[cop];
        tata[cop] = x;
        cop = tmp;
    }
    return x;
}

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

int main(){
    cin>>n>>m;
    for(int i=1; i<=m; ++i)
        cin>>muc[i].u>>muc[i].v>>muc[i].w;
    sort(muc+1, muc+m+1,cmp);   //sortam dupa cost
    for(int i=1; i<=n; ++i)
        tata[i] = i;  //initializam tata cu nodul
    for(int i=1; i<=m; ++i){
        int tu = find_tata(muc[i].u);
        int tv = find_tata(muc[i].v);
        if(tu != tv){
            ans += muc[i].w;
            //cout<<muc[i].w<<' ';
            muc[i].ok = 1;
            tata[tu] = tv;
        }
    }
    //cout<<'\n';
    cout<<ans<<'\n'<<n-1<<'\n';
    for(int i=1; i<=m; i++)
        if(muc[i].ok)
            cout<<muc[i].u<<' '<<muc[i].v<<'\n';
    return 0;
}