#include<iostream>
#include<fstream>
#include<vector>
#include<ctime>
#include<cstdlib>
#define numaru 200001
#define INFILE "apm.in"
#define OUTFILE "apm.out"
using namespace std;
typedef struct {int val,i,j;}MUCHIE;
vector < pair<int, int> > Graf[numaru], MST;
vector < MUCHIE > min_heap;
int n,dim,sum;
bool einMST[numaru];
MUCHIE createMUCHIE(int val,int i,int j)
{
    MUCHIE muchie;
    muchie.val=val;
    muchie.i=i;
    muchie.j=j;
    return muchie;
}

void swapinheap(int i,int j)
{
    MUCHIE auxmuchie;
    auxmuchie=min_heap[i];min_heap[i]=min_heap[j];min_heap[j]=auxmuchie;
}

void min_heapADD(MUCHIE muchie)
{
    if(dim==0)
    {
        min_heap.push_back(muchie);
        dim=1;
    }
    else
    {
        ++dim;
        min_heap.push_back(muchie);
        int i=dim;
        while(i!=1 && min_heap[i].val<min_heap[i/2].val)
        {
            swapinheap(i,i/2);
            i/=2;
        }
    }
}

void min_heapDELETEHEAD()
{
    if(dim==0)return ;
    swapinheap(1,dim);
    min_heap.erase(min_heap.begin()+dim);
    --dim;
    for(int i=1;i*2<=dim;)
    {
        i*=2;
        if(i+1<=dim && min_heap[i+1].val<min_heap[i].val)++i;
        if(min_heap[i].val<min_heap[i/2].val) swapinheap(i,i/2);
        else break;
    }
}
void citire()
{
    ifstream f(INFILE);
    int m,i,j,c;
    f>>n>>m;
    for(;m;--m)
    {
        f>>i>>j>>c;
        Graf[i].push_back(make_pair(j,c));
        Graf[j].push_back(make_pair(i,c));
    }
    f.close();
}

void scrieGraf()
{
    ofstream g(OUTFILE);
    g<<sum<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;++i)g<<MST[i].first<<" "<<MST[i].second<<"\n";
    g.close();
}

void extractMST()
{
    int x;
    MUCHIE muchia;
    ///aleg random un nod start
    ///x=rand()%n+1;
    x=1;///inca nu
    ///il marchez ca fiind in MST
    einMST[x]=true;
    ///ii adaug muchiile adiacente in min_heap
    for(int i=0;i<Graf[x].size();++i)
        min_heapADD(createMUCHIE(Graf[x][i].second,x,i));
    for(int step=n;step!=1;--step)
    {
        do
        {
            muchia=min_heap[1];
            min_heapDELETEHEAD();
        }
        while(einMST[muchia.i] && einMST[Graf[muchia.i][muchia.j].first]);
        ///acum am scos muchie de la muchia.i la Graf[muchia.i][muchia.j].first de valoare Graf[muchia.i][muchia.j].second
        sum+=muchia.val;
        x=Graf[muchia.i][muchia.j].first;
        ///adaug muchia in MST
        MST.push_back(make_pair(muchia.i,x));
        ///il marchez ca fiind in MST
        einMST[x]=true;
        for(int i=0;i<Graf[x].size();++i)
            if(!einMST[Graf[x][i].first])
                min_heapADD(createMUCHIE(Graf[x][i].second,x,i));
    }
}
int main()
{
    min_heap.push_back(createMUCHIE(-1,-1,-1));
    //srand(time(0));

    citire();
    extractMST();
    scrieGraf();
    return 0;
}