#include <fstream>
#include <algorithm>
#define NMAX 400002

using namespace std;

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

int N,M,APM,T[NMAX>>1];
struct muchie{
    int x,y,c;
}V[NMAX];


class cmp
{
    public:
    inline bool operator()(const muchie&a,const muchie&b){return a.c<b.c;}
};
int multime(int x)
{
    if(!T[x])return x;
    return multime(T[x]);
}

int main()
{
    int i,m1,m2;
    in>>N>>M;
    for(i=0;i<M;i++)
        in>>V[i].x>>V[i].y>>V[i].c;
    //sortez muchiile crescator dupa cost

    sort(V,V+M,cmp());
    for(i=0;i<M;i++)
    {
        m1 = multime(V[i].x);
        m2 = multime(V[i].y);
        if(m1!=m2)
        {
            APM+=V[i].c,T[m2]=m1;
        }
    }
    out<<APM<<'\n'<<N-1<<'\n';
    for(i=1;i<=N;i++)
        if(T[i])out<<i<<' '<<T[i]<<'\n';
    return 0;
}