using namespace std;
#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back
#define mkp make_pair
#define INF 0x3f3f3f3f
const int maxn = 200200;
FILE *f=fopen ("apm.in", "r");
FILE *g=fopen ("apm.out", "w");

int VEC[maxn],ANS,V[maxn]; //VEC-vectorul cu capatul muchiilor de cost minim; ANS-costul APM; V-costul muchiei de cost minim
int H[maxn*2+100],POZ[maxn]; //H-Heap, POZ-pozitia in heap
vector <pair <int,int> > VECT[maxn],VANS; //VECT-graful repr prin liste de adiacenta;
//VANS-vectorul solutie
int N,M,L; //L-lungimea heapului

void introduce_in_apm(int x)
{
    for(unsigned int i=0; i<VECT[x].size(); ++i) //parcurgem lista de adiacenta
    {
        int nod=VECT[x][i].first; //extragem nodul vecin lui x
        int cost=VECT[x][i].second; //extragem costul muchiei
        V[nod]=min(V[nod],cost); //aflam muchia incidenta in x de cost minim
        if(V[nod]==cost) VEC[nod]=x; //daca costul minim nu e infinit introduce nodul adiacent cu x in VEC
    }
}

void up_heap(int poz)
{
    while(poz>1 && V[H[poz]]<V[H[poz/2]]) //daca valoarea fiului e mai mica decat valoarea tatalui
    {
        swap(H[poz], H[poz/2]); //interschimbam nodurile in heap
        swap(POZ[H[poz]],POZ[H[poz/2]]); //interschimbam pozitiile
        poz=poz/2; //fiul devine tata
    }
}

void introduce_in_heap (int nod)
{
    H[++L]=nod; //introducem nodul pe ultima pozitie din heap
    POZ[nod]=L; //retinem pozitia
    up_heap(L); //il urcam pe pozitia corecta
}

void down_heap(int poz)
{
    while((poz * 2 <= L && V[H[poz]] > V[H[poz * 2]]) || (poz * 2 + 1 <= L && V[H[poz]] > V[H[poz * 2 + 1]]))
        //daca mai avem fii si tatal este mai mare decat unul din  ei
    {
        if (V[H[poz * 2]] < V[H[poz * 2 + 1]] || poz * 2 + 1 > L)
        //daca fiul stang e mai mic decat cel drept sau cel drept nu exista
        {
            swap(H[poz],H[poz * 2]); //interschimbam tatal si fiul
            swap(POZ[H[poz]],POZ[H[poz * 2]]); //si pozitiile lor
            poz *= 2;//tatal devine fiul stang
        }
        else //fiul drept e mai mic
        {
            swap(H[poz],H[poz * 2 + 1]); //interschimbam tatal si fiul
            swap(POZ[H[poz]],POZ[H[poz * 2 + 1]]);//si pozitiile lor
            poz = poz * 2 + 1;//tatal devine fiul drept
        }
    }
}

int scoate_radacina_heap()
{
    int x=H[1]; //extragem varful
    swap(H[1],H[L]); //interschimbam primul si ultimul nod
    swap(POZ[H[1]],POZ[H[L]]); //interschimbam pozitiile
    L--; //eliminam ultimul nod
    down_heap(1); //pozitionam primul nod in heap
    POZ[x]=0; //pozitia devine nula pentru a nu selecta pentru a doua oara acest nod in apm, riscand sa formam cicluri
    return x;
}


int main()
{
    //citire
    fscanf(f,"%d%d",&N,&M);
    for(int i=1; i<=M; i++)
    {
        int x,y,c;
        fscanf(f,"%d%d%d",&x,&y,&c);
        VECT[x].pb(mkp(y,c));
        VECT[y].pb(mkp(x,c));
    }
    //initializam elementele vectorului de costuri cu INF ca apoi sa putem calcula minimul
    for(int i=1; i<=N; i++)
        V[i]=INF;
    V[1]=0;
    introduce_in_apm(1);
    for(int i=2;i<=N;++i)
        introduce_in_heap(i);

    for(int i=1;i<N;++i)
    {
        int x=scoate_radacina_heap(); //extragem muchia de cost minim
        introduce_in_apm(x);

        ANS+=V[x];//adunam valoarea muchiei minime la costul apm
        VANS.pb(mkp(x,VEC[x])); // introducem capetele muchiei de cost minim in vectorul solutie
        for(unsigned int j=0; j<VECT[x].size();++j) //parcurgem lista de adiacenta a nodului x(care la inceput e un nod adiacent cu 1)
        {
            int nod=VECT[x][j].first; //extragem un vecin
            if(POZ[nod])up_heap(POZ[nod]); //daca vecinul se afla in heap(nu l-am pus in apm), urcam nodul in heap(daca e nevoie)
        }
    }

    fprintf(g,"%d\n",ANS);
    fprintf(g,"%d\n",N-1);
    for(unsigned int i=0; i<N-1; ++i)
        fprintf(g,"%d %d\n", VANS[i].first,VANS[i].second);




    return 0;
}