#include<set>
#include<vector>
#include<fstream>
#define inf 1001
using namespace std;
    ifstream f("apm.in");
    ofstream g("apm.out");
long n,m;
long comp[200001];
struct muchie{ long x,y,c;} v[400001];
vector<muchie> a;

long father(long nod) {return nod/2;}
long right_son(long nod){return 2*nod+1;};
long left_son(long nod){return 2*nod;};

void citire()
{
    long i;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    for(i=1;i<=n;i++)
        comp[i]=i;
}

void coboara_heap(long k)
{
    long son;
    bool coboara;
    do{
        coboara=false;
        son=0;
        if(v[left_son(k)].c<v[right_son(k)].c)
           son=left_son(k);
        else
            son=right_son(k);
        if(son==m+1)
            son--;
        if(v[k].c > v[son].c && son<=m)
            {
                swap(v[k],v[son]);
                k=son;
                coboara=true;
            }
    }while(coboara==true);
}

void creare_heap()
{
    for(long i=m/2;i>0;--i)
        coboara_heap(i);
}

void kruskal()
{
    long i,sum=0,ma,mi;
    while(m)
    {
        if(comp[v[1].x]!=comp[v[1].y])
        {
            sum+=v[1].c;
            a.push_back(v[1]);
            if(comp[v[1].x]<comp[v[1].y])
                {ma=comp[v[1].y];
                mi=comp[v[1].x];
                comp[v[1].y]=comp[v[1].x];}
            else
                {ma=comp[v[1].x];
                mi=comp[v[1].y];
                comp[v[1].x]=comp[v[1].y];}
            for(i=1;i<=n;i++)
                if(comp[i]==ma)
                    comp[i]=mi;
        }
        while(comp[v[m].x]==comp[v[m].y] && m!=0)
            m--;
        swap(v[1],v[m]);
        if(m) m--;
        coboara_heap(1);
    }
    g<<sum<<'\n';
    g<<a.size()<<'\n';
    for(long i=0;i<a.size();i++)
        g<<a[i].x<<" "<<a[i].y<<'\n';
}

int main()
{

citire();
creare_heap();
kruskal();

return 0;
}