#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

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

int parinte[200002],card[200002];

struct muchii{
    int a,b,c;
};
muchii v[400002];

bool cmp(muchii a, muchii b){
    return a.c < b.c;
}

int fnd(int x){
    if(parinte[x]==x)
        return x;
    parinte[x]=fnd(parinte[x]);
    return parinte[x];
}
void unire(int x,int y){
    x=fnd(x); y=fnd(y);
    if(x==y)
    return;

    if(card[x]<card[y])
    swap(x,y);
    parinte[y]=x;
    card[x]+=card[y];
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        card[i]=1;
        parinte[i]=i;
    }
    for(int i=1;i<=m;i++)
    cin>>v[i].a>>v[i].b>>v[i].c;

    sort(v+1,v+m+1,cmp);
    queue <pair<int,int>> q;
    int cost=0;

    for(int i=1;i<=m;i++){
        if(fnd(v[i].a)!=fnd(v[i].b)){
            cost+=v[i].c;
            unire(v[i].a,v[i].b);
            q.push({v[i].a,v[i].b});
        }
    }
    cout<<cost<<"\n"<<n-1<<"\n";
    while(q.empty()== false){
        cout<<q.front().first<<" "<<q.front().second<<endl;
        q.pop();
    }
}