#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int sef[200005];

struct muchie
{
    int x,y,c;
}v[400005],sol[200005];

bool cmp(muchie a, muchie b)
{
    if(a.c>b.c)
        return false;
    return true;
}

int sefsup(int bla)
{
    if(sef[bla]==bla)
        return bla;
    else
        return sef[bla]=sefsup(sef[bla]);
}
void unire(int bla1, int bla2)
{
    int sefs1=sefsup(bla1),sefs2=sefsup(bla2);
    sef[sefs1]=sefs2;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i,cost=0,nrsol=0;
    cin>>n>>m;
    for(i=1;i<=m;i++)
        cin>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;i++)
        sef[i]=i;
    for(i=1;i<=m;i++)
    {
        if(sefsup(v[i].x)!=sefsup(v[i].y))
        {
            unire(v[i].x,v[i].y);
            cost+=v[i].c;
            sol[++nrsol]=v[i];
        }
    }
    cout<<cost<<"\n"<<n-1<<"\n";
    for(i=1;i<=n-1;i++)
        cout<<sol[i].x<<" "<<sol[i].y<<"\n";
    return 0;
}