#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,x,y,r1,r2,a[400004],k,s;
struct idk
{
    int x,y,z;
};
idk v[400004],v1[400004];
bool cmp(idk x,idk y)
{
    if(x.z<y.z)
        return true;
    return false;
}
int aflrad(int z)
{
    while(a[z]!=0)
    {
        z=a[z];
    }
    return z;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].z;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        x=v[i].x;
        y=v[i].y;
        r1=aflrad(x);
        r2=aflrad(y);
        if(r1==r2)
            continue;
        s+=v[i].z;
        if(r1<r2)
        {
            a[r2]=r1;
            v1[++k].x=x;
            v1[k].y=y;
        }
        else
        {
            a[r1]=r2;
            v1[++k].x=x;
            v1[k].y=y;
        }
    }
    fout<<s<<"\n"<<k<<"\n";
    for(int i=1;i<=k;i++)
        fout<<v1[i].y<<" "<<v1[i].x<<"\n";
    return 0;
}