#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f ("apm.in");
ofstream t ("apm.out");

struct muchie{
    int from,to,cost;
};

int n,m,cost_total,cont,rad[200010];

vector <muchie> v,sol;

int main()
{
    f>>n>>m;
    for (int i=1;i<=n;++i)
        rad[i]=i;
    for (int x,y,c,i=0;i<m;++i)
        f>>x>>y>>c,
        v.push_back({x,y,c});
    sort(v.begin(),v.end(),[](muchie a,muchie b){return a.cost<b.cost;});
    for (vector <muchie>::iterator it=v.begin();cont<n-1;++it){
        int x=it->from,y=it->to,aux;
        while (x!=rad[x]) aux=rad[rad[x]],rad[x]=aux,x=aux;
        while (y!=rad[y]) aux=rad[rad[y]],rad[y]=aux,y=aux;
        if (x!=y)
            ++cont,
            rad[x]=y,
            cost_total+=it->cost,
            sol.push_back(*it);
    }
    t<<cost_total<<'\n'<<cont<<'\n';
    for (auto i:sol)
        t<<i.from<<" "<<i.to<<'\n';
    return 0;
}