#include <fstream>
#include <list>
#include <queue>
#define DIM 200001

using namespace std;

int n,m,x,y,c,nr=1,cr,hp,cost;
list<pair<int,int> > nod[DIM];
queue<int> cd;
std::pair<pair<int,int> ,int> Heap[DIM];
std::pair<int,int> sol[DIM];
bool v[DIM];

void addHeap(std::pair<pair<int,int>,int> x)
{
    ++hp;
    Heap[hp]=x;
    int poz=hp;
    while(Heap[poz].second<Heap[poz/2].second && poz>1)
    {
        swap(Heap[poz],Heap[poz/2]);
        poz=poz/2;
    }
}
void delHeap()
{
    int poz=1;
    Heap[1]=Heap[hp];
    --hp;
    while((Heap[poz].second>Heap[poz*2].second || Heap[poz].second>Heap[poz*2+1].second) && poz*2<=hp)
    {
        if(Heap[poz*2].second <Heap[poz*2+1].second || poz*2+1 >hp)
        {
            swap(Heap[poz],Heap[poz*2]);
            poz=poz*2;
        }
        else
        {
            swap(Heap[poz],Heap[poz*2+1]);
            poz=poz*2+1;
        }
    }
}

void parcurgere(int k)
{
    cd.push(k);
    while(!cd.empty())
    {
        int vf=cd.front();
        v[vf]=1;
        cd.pop();
        for(list<pair<int,int> >::iterator i=nod[vf].begin();i!=nod[vf].end();++i)
        {
            std::pair<int,int> z=*i;
            if(!v[z.first])
            addHeap(make_pair(make_pair(vf,z.first),z.second));
        }
        std::pair<int,int> x=Heap[1].first;
        while(v[x.second] && hp!=0)
        {
            delHeap();
            x=Heap[1].first;
        }
        if(!v[x.second])
        {
            cd.push(x.second);
            cost+=Heap[1].second;
            sol[++cr]=x;
        }
        delHeap();
    }
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        nod[x].push_back(make_pair(y,c));
        nod[y].push_back(make_pair(x,c));
    }
    parcurgere(1);
    g<<cost<<'\n';
    g<<cr<<'\n';
    for(int i=1;i<=cr;++i)
    g<<sol[i].first<<" "<<sol[i].second<<'\n';
    f.close();
    g.close();
    return 0;
}