#include <fstream>
#include<vector>
#include<algorithm>
#include<list>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int p[800003],r[800003],n,m,cost,componente;

struct muchie{int x; int y; int c;};

vector<muchie>v;
list<pair<int, int> >sol;

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

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

int Union(int x, int y)
{
    int xroot,yroot;
    xroot=Find(x);
    yroot=Find(y);
    if(xroot==yroot) return 0;
    if(r[yroot]>=r[xroot])
    {
        p[xroot]=p[yroot];
        r[yroot]+=r[xroot];
    }
    else
    {
        p[yroot]=p[xroot];
        r[xroot]+=r[yroot];
    }
    componente--;
}

int main()
{
    int x,y,c,i;
    muchie aux;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        aux.x=x;
        aux.y=y;
        aux.c=c;
        v.push_back(aux);
    }
    sort(v.begin(),v.end(),cond);
    for(i=1;i<=m;i++) {
        r[i]=1;
        p[i]=i;
    }
    vector<muchie>::iterator it;
    componente=n;
    for(it=v.begin();it!=v.end();++it)
    {
        if(componente==1) break;
        aux=*it;
        x=aux.x; y=aux.y; c=aux.c;
        if(Find(x)!=Find(y))
        {
            cost+=c;
            sol.push_back(make_pair(x,y));
            Union(x,y);
        }
    }
    g<<cost<<'\n';
    g<<sol.size()<<'\n';
    list<pair<int, int> >::iterator it1;
    for(it1=sol.begin();it1!=sol.end();++it1) g<<it1->first<<' '<<it1->second<<'\n';
    f.close();
    g.close();
    return 0;
}