#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct muchie{
    int x,y;
    short c;
}a[400010];
int n,m,i,j,nrm,s,st,dr,minn,maxx,v[200010];
bool viz[400010];
int comp(muchie i, muchie j)
{
    if(i.c<=j.c)
        return 1;
    else
        return 0;
}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a[i].x>>a[i].y>>a[i].c;
    }
    sort(a+1,a+m+1,comp);
    for(i=1;i<=n;i++)
    {
        v[i]=i;
    }
    for(i=1;nrm<n-1;i++)
    {
        if(v[a[i].x]!=v[a[i].y])
        {
            minn=min(v[a[i].x],v[a[i].y]);
            maxx=max(v[a[i].x],v[a[i].y]);
            nrm++;
            viz[i]=1;
            s+=a[i].c;
            for(j=1;j<=n;j++)
                if(v[j]==maxx)
                    v[j]=minn;
        }
    }
    fout<<s<<'\n'<<nrm<<'\n';
    for(i=1;i<=m;i++)
    {
        if(viz[i]==1)
        {
            fout<<a[i].x<<' '<<a[i].y<<'\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}