#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,i,s;
struct apm{
    int nod1,nod2,cost;
};
apm muchii[400001];
bool cmp(apm a,apm b){
    return (a.cost < b.cost);
}
apm sol[200001];
int sef[200001];
int sef_suprem(int x){
    if (sef[x]==x)
        return x;
    else
        return sef[x]=sef_suprem(sef[x]);

}
void unire(int x,int y){
    int sef1=sef_suprem(x);
    int sef2=sef_suprem(y);
    sef[sef2]=sef[sef1];
}
int main(){
    fin>>n>>m;
    for (i=1;i<=m;i++)
        fin>>muchii[i].nod1>>muchii[i].nod2>>muchii[i].cost;
    sort(muchii+1,muchii+m+1,cmp);
    for (i=1;i<=n;i++)
        sef[i]=i;
    int j=0;
    for (i=1;i<=m;i++){
        if (sef_suprem(muchii[i].nod1)!=sef_suprem(muchii[i].nod2)){
            unire(muchii[i].nod1,muchii[i].nod2);
            sol[++j].nod1=muchii[i].nod1;
            sol[j].nod2=muchii[i].nod2;
            s+=muchii[i].cost;
        }
    }
    fout<<s<<'\n'<<n-1<<'\n';
    for (i=1;i<=j;i++)
        fout<<sol[i].nod1<<' '<<sol[i].nod2<<'\n';
    return 0;
}