#include <fstream>
#include <algorithm>
#define nmax (int)(2e5+1)
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,t[nmax],M,cost;
struct muchie{
    int x,y,c;
    bool in;
}mch[nmax*2];
bool cmp(const muchie& a,const muchie& b){
    return a.c<b.c;
}
int get_root(int x){
    if(t[x]>0)
        return get_root(t[x]);
    return x;
}
void join(int x,int y,int c,int ind){
    x=get_root(x),y=get_root(y);
    if(x==y)
        return;
    M++;
    cost+=c;
    mch[ind].in=1;
    if(t[x]>t[y])
        swap(x,y);
    t[x]+=t[y];
    t[y]=x;
}
void kruskal(){
    sort(mch+1,mch+m+1,cmp);
    for(int i=1;i<=m;i++){
        join(mch[i].x,mch[i].y,mch[i].c,i);
        if(M==n-1)
            break;
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        t[i]=-1;
    for(int i=1;i<=m;i++)
        cin>>mch[i].x>>mch[i].y>>mch[i].c;
    kruskal();
    cout<<cost<<'\n'<<n-1<<'\n';
    for(int i=1;i<=m;i++)
        if(mch[i].in)
            cout<<mch[i].x<<" "<<mch[i].y<<'\n';
    return 0;
}
/// Kruskal