#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

class multime
{
    int *elem,dim;
public:
    multime()
    {
        dim = 0;
    }
    multime(int x)
    {
        dim = 1;
        elem = new int[1];
        elem[0] = x;
    }
    int& operator[](int x)
    {
        return elem[x];
    }
    multime* operator+ (multime x)
    {
        multime* a = new multime();
        (*a).set_dim(dim + x.get_dim());
        for(int i=0;i<dim;++i)
        {
            (*a)[i] = elem[i];
        }
        for(int i=dim;i<dim+x.get_dim();++i)
        {
            (*a)[i] = x[i-dim];
        }
        return a;
    }
    int get_dim()
    {
        return dim;
    }
    void set_dim(int x)
    {
        dim = x;
        elem = new int[dim];
    }

};

ostream& operator<<(ostream& o,multime& x)
{
    for(int i=0;i<x.get_dim();++i)
    {
            o<<x[i]<<" ";
    }
    o<<"\n";
    return o;
}

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

struct muchie
{
    int a,b,c;
};

struct comparator
{
    bool operator() (muchie i,muchie j)
    {
        return i.c > j.c;
    }
};

int main()
{
    priority_queue<muchie,vector<muchie>,comparator> minHeap;
    int n,m,arb = 0,arb_i = 0;
    int cost = 0;
    f>>n>>m;
    multime** v = new multime*[n+1];
    multime* p;
    muchie* muc = new muchie[m];
    muchie* arbore = new muchie[n-1];
    muchie x;

    for(int i=0;i<=n;++i)
    {
        v[i] = new multime(i);
    }
    for(int i=0;i<m;++i)
    {
        f>>muc[i].a;
        f>>muc[i].b;
        f>>muc[i].c;
        minHeap.push(muc[i]);
    }
    while(arb<n-1)
    {
        x = minHeap.top();
        minHeap.pop();
        if( v[x.a] != v[x.b] )
        {
            cost += x.c;
            ++arb;
            arbore[arb_i] = x;
            ++arb_i;
            p = *(v[x.a]) + (*(v[x.b]));
            cout<<(*p);
            for(int i=0;i<((*(v[x.a])).get_dim());++i)
            {
                if((*(v[x.a]))[i] != x.a)
                   {
                       v[ (*(v[x.a]))[i] ] = p;
                   }
            }
            for(int i=0;i<((*(v[x.b])).get_dim());++i)
            {
                if((*(v[x.b]))[i] != x.b)
                   {
                       v[ (*(v[x.b]))[i] ] = p;
                   }
            }
            v[x.a] = p;
            v[x.b] = p;
        }
    }
    g<<cost<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;++i)
    {
        g<<(arbore[i]).a<<" "<<(arbore[i]).b<<"\n";
    }
    return 0;
}