#include <fstream>
#include <algorithm>
#define nmax (int)(2e5+1)
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,mch,cost,t[nmax];
bool ok[2*nmax];
struct muchie{
    int x,y,c;
}v[2*nmax];
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 nr,int c){
    int rx=get_root(x),ry=get_root(y);
    if(rx==ry)
        return ;
    ok[nr]=1;
    mch++;
    cost+=c;
    if(t[rx]>t[ry])
        swap(rx,ry);
    t[rx]+=t[ry];
    t[ry]=rx;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>v[i].x>>v[i].y>>v[i].c;
    for(int i=1;i<=n;i++)
        t[i]=-1;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=m&&mch!=n-1;i++)
        join(v[i].x,v[i].y,i,v[i].c);
    cout<<cost<<'\n'<<n-1<<'\n';
    for(int i=1;i<=m;i++)
        if(ok[i])
            cout<<v[i].x<<" "<<v[i].y<<'\n';
    return 0;
}