#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,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++)
    {
        st=min(a[i].x,a[i].y);
        dr=max(a[i].x,a[i].y);
        if(v[st]!=v[dr])
        {
            minn=min(v[st],v[dr]);
            nrm++;
            viz[i]=1;
            s+=a[i].c;
            v[st]=minn;
            j=dr+1;
            while(v[j]==v[dr])
            {
                v[j]=v[st];
                j++;
            }
            v[dr]=v[st];
        }
    }
    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;
}