#include <fstream>
#include <algorithm>
using namespace std;

#define NMax 200005
#define MMax 400005

ifstream f("apm.in");
ofstream g("apm.out");

int n,m;
int tata[NMax];

struct muchie
{
    int a,b,c;
};
bool Compare(muchie i,muchie j) {return i.c<j.c;}

muchie M[MMax],sol[NMax];
int nrsol,sum;

int query(int x)
{
    if(!tata[x]) return x;
    tata[x]=query(tata[x]);
    return tata[x];
}

void update(int x,int y)
{
    tata[x]=y;
}

int main()
{
    int i,q1,q2;

    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>M[i].a>>M[i].b>>M[i].c;
    }

    sort(M+1,M+m+1,Compare);

    for(i=1;i<=m && nrsol<n-1;i++)
    {
        q1=query(M[i].a);
        q2=query(M[i].b);
        if( q1!=q2 )
        {
            update(q1,q2);
            ++nrsol;
            sol[nrsol].a=M[i].a;
            sol[nrsol].b=M[i].b;
            sum+=M[i].c;
        }
    }

    g<<sum<<"\n"<<nrsol<<"\n";
    for(i=1;i<=nrsol;++i) g<<sol[i].b<<" "<<sol[i].a<<"\n";

    f.close();
    g.close();
    return 0;
}