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

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

int tata[400001],siz[400001];

struct muchie{
    int a,b,cost;
} v[200001];
vector<pair<int,int>> rasp;

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

int find_tata(int a){
    if(a!=tata[a]) tata[a]=find_tata(tata[a]);
    return tata[a];
}

int main()
{
    int n,m,i,tata1,tata2,costt=0;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        tata[i]=i;
        siz[i]=1;
    }
    for(i=1;i<=m;i++){
        cin>>v[i].a>>v[i].b>>v[i].cost;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m;i++){
        tata1=find_tata(v[i].a);
        tata2=find_tata(v[i].b);
        if(tata1!=tata2){
            costt+=v[i].cost;
            tata[tata2]=tata1;
            siz[tata1]+=siz[tata2];
            rasp.push_back({v[i].a,v[i].b});
            if(siz[tata1]==n) break;
        }
    }
    cout<<costt<<"\n"<<rasp.size()<<"\n";
    for(i=0;i<rasp.size();i++){
        cout<<rasp[i].first<<" "<<rasp[i].second<<"\n";
    }
    return 0;
}