#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

const int MAX = 2e5 + 1;

int n , m;

struct muchie{

    int x , y , c;

};

vector <muchie> g;
vector<pair<int,int>> ans;

bool cmp( muchie a , muchie b ){

    return a.c < b.c;
}

struct DSU{

    int t[MAX] , h[MAX];

    void init(){

        for(int i = 1 ; i <= n ; i++){

            t[i] = h[i] = 0;
        }
    }

    int findc( int x ){

        int r = x , aux;

        while(t[x]){

            x = t[x];
        }

        swap(r,x);

        while(t[x]){

            aux = t[x];

            t[x] = r;

            x = aux;
        }

        return r;
    }

    void unionp( int x , int y ){

        if(h[x] == h[y]){

            t[x] = y;

            h[y]++;

        }else{

            if(h[x] > h[y]){

                swap(x,y);
            }

            t[x] = y;
        }
    }

}uf;

int main(){

    cin >> n >> m;

    uf.init();

    muchie aux;

    while(m--){

        cin >> aux.x >> aux.y >> aux.c;

        g.push_back(aux);
    }

    sort(g.begin(),g.end(),cmp);

    int ct = 0;

    int nrn = n-1;

    int sz = g.size();

    muchie it;

    for(int i = 0 ; i < sz && nrn ; i++){

        it.x = uf.findc(g[i].x);
        it.y = uf.findc(g[i].y);

        if(it.x == it.y) continue;

        nrn--;

        ans.push_back({g[i].x,g[i].y});

        ct += g[i].c;

        uf.unionp(it.x,it.y);
    }

    cout << ct << '\n';

    cout << ans.size() << '\n';

    for(auto it : ans){

        cout << it.first << ' ' << it.second << '\n';
    }

    return 0;
}