#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muc
{
  int x,y,c;
}v[200001];
int i,j,n,m,cost,s,nr,h[200001],k;
bool viz[200001];
int father(int x)
{
    if (x != h[x])
        h[x] = father(h[x]);
    return h[x];
}

bool cmp(const muc a,const muc b)
{
    return a.c<b.c;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
        fin>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;++i)
        h[i]=i;
    k=1;
    for(i=1;i<n;++i)
    {
        while(father(v[k].x)==father(v[k].y))
            ++k;
        h[father(v[k].y)] = father(v[k].x);
        viz[k] = true;
        s += v[k].c;
        ++k;
    }
    fout<<s<<'\n';
    fout<<n-1<<'\n';
    for(i=1;i<=m;++i)
        if(viz[i])
            fout<<v[i].x<<" "<<v[i].y<<'\n';

    return 0;
}