#include <bits/stdc++.h>
#define LMAX 400005
using namespace std;
struct Muchie{
    int u,v,cost;
    bool operator <(const Muchie &other) const{
        return cost<other.cost;
    }
}v[LMAX];
#define NMAX 200005
int n,T[NMAX],R[NMAX];
void Init(){
    for(int i=1;i<=n;++i){
        T[i]=i;
        R[i]=1;
    }
}
int Find(int x){
    int r=x;
    while(r!=T[r])
        r=T[r];
    while(x!=r){
        int urm=T[x];
        T[x]=r;
        x=urm;
    }
    return r;
}
void Union(int x,int y){
    int r_x=Find(x),r_y=Find(y);
    if(r_x==r_y)
        return ;
    if(R[r_x]<R[r_y])
        T[r_x]=r_y;
    else{
        T[r_y]=r_x;
        if(R[r_x]==R[r_y])
            ++R[r_x];
    }
}
int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%d %d %d",&v[i].u,&v[i].v,&v[i].cost);
    sort(v+1,v+m+1);
    Init();
    int cost_apm=0;
    vector<Muchie> apm;
    for(int i=1;i<=m;++i){
        if(Find(v[i].u)!=Find(v[i].v)){
            cost_apm+=v[i].cost;
            apm.push_back(v[i]);
            Union(v[i].u,v[i].v);
        }
    }
    printf("%d\n",cost_apm);
    printf("%d\n",n-1);
    for(auto it : apm)
        printf("%d %d\n",it.u,it.v);
    return 0;
}