#include <fstream>
#include <algorithm>
#define NMAX 200010
#define MMAX 400010
using namespace std;
int n,m,i,nivele[NMAX],t[NMAX];
struct muchie{
    int a,b,cost;
}v[MMAX],sol[NMAX];
ifstream f("apm.in");
ofstream g("apm.out");

inline bool cmp(muchie x,muchie y){
    return (x.cost<y.cost);
}
int gasesc(int x){
    if(x==t[x])
        return x;
    t[x]=gasesc(t[x]);
    return t[x];
}
void unesc(int x,int y){
    if(nivele[x]<nivele[y])
        t[x]=y;
    else{
        if(nivele[x]>nivele[y])
            t[y]=x;
        else{
            t[x]=y;
            ++nivele[y];
        }
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>v[i].a>>v[i].b>>v[i].cost;
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;i++){
        t[i]=i;
        nivele[i]=1;
    }
    int j=1,s=0,x,y;
    for(i=1;i<n;i++){
        while((x=gasesc(v[j].a))==(y=gasesc(v[j].b)))
            j++;
        s+=v[j].cost;
        unesc(x,y);
        sol[i]=v[j];
        j++;

    }
    g<<s<<'\n'<<n-1<<'\n';
    for(i=1;i<n;i++)
        g<<sol[i].a<<" "<<sol[i].b<<'\n';
    return 0;
}