#include <fstream>
#include <algorithm>
#define nmax 200005
#define mmax 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie {
    int x,y,cost;
}v[mmax];

bool cmp(const muchie &a,const muchie &b)
{
    return a.cost<b.cost;
}

int t[nmax],n,m;
bool ok[nmax];

int rad(int nod)
{
    while(t[nod]>0)
        nod=t[nod];
    return nod;
}


int main()
{
    int i,x,y,c,r1,r2,cost=0,nr=0;
    fin>>n>>m;
    for(i=1;i<=m;i++) {
        fin>>x>>y>>c;
        v[i].x=x;
        v[i].y=y;
        v[i].cost=c;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;i++)
        t[i]=-1;
    for(i=1;i<=m;i++)
    {
        r1=rad(v[i].x);
        r2=rad(v[i].y);
        if(r1!=r2)
        {
            cost+=v[i].cost;
            ok[i]=true;
            nr++;
            if(nr==n-1)
                break;
            if(t[r1]<t[r2])
            {
                t[r1]+=t[r2];
                t[r2]=r1;
            }
            else
            {
                t[r2]+=t[r1];
                t[r1]=r2;
            }
        }
    }
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(i=1;i<=m;i++)
        if(ok[i]==true)
            fout<<v[i].x<<" "<<v[i].y<<'\n';
    return 0;
}