#include <fstream>
#define NMAX 200000
#include <algorithm>
using namespace std;
int n,m,t[NMAX+10],nivele[NMAX+10];
struct muchie{
int a,b,cost;
}v[2*NMAX+100],sol[NMAX+100];
ifstream f("apm.in");
ofstream g("apm.out");
bool cmp(muchie a,muchie b){
    return(a.cost<b.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(int i=1;i<=m;i++)
        f>>v[i].a>>v[i].b>>v[i].cost;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;i++){
        t[i]=i;
        nivele[i]=1;
    }
    int j=1,a,b,s=0;
    for(int i=1;i<n;i++){
        while((a=gasesc(v[j].a))==(b=gasesc(v[j].b)))
            j++;
        s+=v[j].cost;
        unesc(a,b);
        sol[i]=v[j];
        j++;
    }
    g<<s<<'\n'<<n-1<<'\n';
    for(int i=1;i<n;i++)
        g<<sol[i].b<<" "<<sol[i].a<<'\n';
    return 0;
}