#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define NMAX 200000
#define MMAX 400000
struct muchie
{
    int vf1;
    int vf2;
    int cost;
};

muchie t[MMAX];

vector <muchie> q;
bool comp(muchie a, muchie b)
{
    return a.cost<b.cost;
}

struct nod
{
    nod* father;
    int rang;

};
nod* v[NMAX];
nod* papi(nod* a)
{
    if(a->father==nullptr)
        return a;
    return papi(a->father);
}
void join(nod* a, nod* b)
{
    a=papi(a);
    b=papi(b);
    if(a->rang<b->rang)
        a->father=b;
    else if(a->rang>b->rang)
        b->father=a;
    else
    {
        a->father=b;
        b->rang++;
    }
}
int main()
{
    int n;
    int m;
    f>>n>>m;
    int total=0;


    for(int i=1;i<n+1;i++)
    {
        v[i]=new nod;
        v[i]->father=nullptr;
        v[i]->rang=1;
    }
    for(int i=0;i<m;i++)
    {

        int x,y,c;
        f>>x>>y>>c;
        t[i].vf1=x;
        t[i].vf2=y;
        t[i].cost=c;
    }
    sort(t,t+m,comp);
    for(int i=0;i<m;i++)
    {
        if(papi(v[t[i].vf1])!=papi(v[t[i].vf2]))
        {
            join( v[t[i].vf1],v[t[i].vf2] );
            q.push_back(t[i]);
            total=total+t[i].cost;
        }

    }
    g<<total<<"\n"<<q.size()<<"\n";
    for(int i=0;i<q.size();i++)
        g<<q[i].vf1<<' '<<q[i].vf2<<"\n";
    return 0;
}