#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
const int maxn=200001;
const int maxm=400001;
int parinti[maxn];
int in[maxn];
struct muchie
{
    int x;
    int y;
    int c;
};
muchie mu[maxm];
int sol[maxn];
bool compara(muchie a,muchie b)
{
    if (a.c==b.c) return a.x<b.x;
    else return a.c<b.c;
}
void build(int n)
{
    int i;
    for (i=1;i<=n;i++){
        parinti[i]=i;
        in[i]=1;
    }
}
int gasire(int x)
{
    while(x!=parinti[x]){ x=parinti[x];}
    return x;
}
void unire(int x,int y)
{
    if (in[x]<in[y]) parinti[x]=y;
    else if(in[y]<in[x]) parinti[y]=x;
    else{
        parinti[y]=x;
        in[x]++;
    }
}
int main()
{
    int n,i,m,s=0,j=0;
    cin>>n>>m;
    build(n);
    for (i=0;i<m;i++){
        cin>>mu[i].x>>mu[i].y>>mu[i].c;
    }
    sort(mu,mu+m,compara);
    for (i=0;i<m;i++){
        if (gasire(mu[i].x)==gasire(mu[i].y)) continue;
        else{
            unire(gasire(mu[i].x),gasire(mu[i].y));
            s+=mu[i].c;
            sol[j]=i;
            j++;
        }
    }
    cout<<s<<"\n";
    cout<<n-1<<"\n";
    for (i=0;i<j;i++){
        cout<<mu[sol[i]].x<<" "<<mu[sol[i]].y<<"\n";
    }
    return 0;
}