#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,b,c,p[200005],heap[200005],v[200005],capat[200005];
int d,mn,inf=(1<<30),start,cost,fr[200005],l,a,last;
vector< pair<int,int> >vecini[200005],mf;

void up(int poz)
{
    while(poz>1 && v[heap[poz]]<v[heap[poz/2]])
    {
        swap(p[heap[poz]],p[heap[poz/2]]);
        swap(heap[poz],heap[poz/2]);
        poz/=2;
    }
}

void down(int poz)
{
    bool ok=true;
    while(ok)
    {
        ok=false;
        mn=inf;
        if(poz*2<=l && v[heap[poz*2]]<mn) mn=v[heap[poz*2]], d=poz*2;
        if(poz*2+1<=l && v[heap[poz*2+1]]<mn) mn=v[heap[poz*2+1]], d=poz*2+1;
        if(mn<v[heap[poz]])
        {
            swap(p[heap[poz]],p[heap[d]]);
            swap(heap[d],heap[poz]);
            poz=d;
            ok=true;
        }
    }
}

void introd()
{
    ++l;
    heap[l]=start;
    p[start]=l;
    v[start]=c;
    up(l);
}

void update(int x)
{
    for(int i=0;i<vecini[x].size();++i)
    {
        start=vecini[x][i].first;
        c=vecini[x][i].second;
        if(fr[start]==0 && c<v[start])
        {
            capat[start]=x;
            if(p[start]==0) introd();
            else
            {
                v[start]=-inf;
                up(p[start]);
                v[start]=c;
                down(1);
            }
        }
    }
}

void elimina(int poz)
{
    last=start=heap[poz];
    fr[start]=1;
    cost+=v[start];
    v[start]=-inf;
    mf.push_back(make_pair(start,capat[start]));
    heap[poz]=heap[l];
    p[heap[poz]]=1;
    --l;
    down(poz);
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>a>>b>>c;
        vecini[a].push_back(make_pair(b,c));
        vecini[b].push_back(make_pair(a,c));
    }
    fr[1]=1;
    for(int i=2;i<=n;++i) v[i]=inf;
    update(1);
    for(int i=2;i<=n;++i)
    {
        elimina(1);
        update(last);
    }
    g<<cost<<'\n';
    g<<mf.size()<<'\n';
    for(int i=0;i<mf.size();++i)
    {
        g<<mf[i].first<<' '<<mf[i].second<<'\n';
    }
    return 0;
}