#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];
    int rad( int x )
    {
        if(!t[x]) return x;
        t[x] = rad(t[x]);
        return t[x];
    }
    void un( int x , int y )
    {
        x = rad(x);
        y = rad(y);
        if(x!=y) t[x] = y;
    }
}uf;

int main(){

    cin >> n >> m;

    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.rad(g[i].x);
        it.y = uf.rad(g[i].y);

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

        nrn--;

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

        ct += g[i].c;

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

    cout << ct << '\n';

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

    for(auto it : ans){

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

    return 0;
}