#include <fstream>
#include<vector>
#include<algorithm>
#include <assert.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{int x; int y; int c;};
int n,m,p[500002],r[500002],cost,componente,ka;

muchie v[500002];
pair<int, int> a[500002];

bool cond(muchie m1, muchie m2)
{
    return (m2.c>=m1.c);
}

int Find(int x)
{   assert (x<=n);
    if(p[x]!=x) p[x]=Find(p[x]);
    return p[x];
}

void Union(int x, int y)
{
    int xroot, yroot;
    xroot=Find(x);
    yroot=Find(y);
    if(xroot==yroot) return;
    if(r[xroot]<r[yroot])
    {
        r[yroot]+=r[xroot];
        p[xroot]=yroot;
    }
    else
    {
        r[xroot]+=r[yroot];
        p[yroot]=xroot;
    }
}

int main()
{
    f>>n>>m;
    componente=n;
    int i,x,y,c;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        muchie aux={x,y,c};
        v[i]=aux;
    }
    sort(v+1,v+m+1,cond);

    for(i=1;i<=n;i++)
    {
        r[i]=1;
        p[i]=i;
    }
    for(i=1;i<=m;++i)
    {
        int x,y,c;
        x=v[i].x; y=v[i].y; c=v[i].c;
        if(Find(x)!=Find(y))
        {
            cost+=c;
            a[++ka]=make_pair(x,y);
            Union(x,y);
        }
    }

    g<<cost<<'\n'<<ka<<'\n';

    for(i=1;i<=ka;++i)
        g<<a[i].first<<' '<<a[i].second<<'\n';
    f.close();
    g.close();
    return 0;
}