#include <cstdio>
#define NMAX 200001
#define MMAX 400001
// min-Heap

using namespace std;
FILE * fin=fopen("apm.in", "r");
FILE * fout=fopen("apm.out", "w");

struct  STR{int x, y, c; };
STR G[MMAX];
int H[MMAX];
int n, m;
int tata[NMAX];
int h[NMAX];
long long int cost;
int A[NMAX]; //=indici muchilor selectate in APM

void citire ();
void afisare ();
void insertheap(int H[NMAX], int&n, int x);
void combine(int H[NMAX], int n, int i);
void create_heap_combine(int H[NMAX], int& n);
//void write_heap(int H[NMAX], int n);
int extractmin(int H[NMAX], int &n);
int Find (int x);
void Union (int i, int j);

int main()
{
    int i, nr=0, cx, cy, mmin;
    citire();
    create_heap_combine(H, m);
    //write_heap(H, m);
    while (nr<n-1)
    {
        mmin=extractmin(H, m);
        cx=Find(G[mmin].x);
        cy=Find(G[mmin].y);
        if(cx!=cy)
        {
            ++nr;
            A[nr]=mmin;
            cost+=G[mmin].c;
            Union(cx, cy);
        }
    }
    afisare();
return 0;
}

void citire ()
{
    int i;
    fscanf(fin, "%d %d\n", &n, &m);
    for(i=1; i<=m; ++i)
    {
        fscanf(fin, "%d %d %d\n", &G[i].x, &G[i].y, &G[i].c);
    }
}

void insertheap(int H[NMAX], int& n, int x) // heap-ul in care inserez, dimensiunea heap-ului, inserez val x
{
// heap-ul in care inserez, dimensiunea heap-ului, inserez val x
int fiu, tata;
fiu=++n; tata=fiu/2;
// tata=fiu>>1
while (tata && H[tata]>x)
    {
        H[fiu]=H[tata];
        fiu=tata;
        tata=fiu/2;
        // tata=fiu>>1
    }
H[fiu]=x;
}


void combine(int H[NMAX], int n, int i)
// se combina nodul H[i] cu Heapurile cu radacinile 2i si 2i+1, obtinand un nou heap cu radacina H[i]
{
int x=H[i], tata, fiu;
tata=i; fiu=2*i;
while (fiu<=n)
    {
        if (fiu+1<=n && G[H[fiu+1]].c<G[H[fiu]].c) fiu++;
        // fiu indica cel mai mic dintre fii
        if (G[H[fiu]].c<G[x].c)
            {
                H[tata]=H[fiu];
                tata=fiu;
                fiu=tata*2;
            }
            else break;
    }
H[tata]=x;
}

void create_heap_combine(int H[NMAX], int& n)
{
int i;
for(i=1; i<=n; ++i)
    H[i]=i;
for (i=n/2; i>0; --i)
    combine(H, n, i);
}

int extractmin(int H[NMAX], int &n)
{
int minim=H[1];
H[1]=H[n--];
combine(H, n, 1);
return minim;
}

int Find (int x)
{
    int aux, rad=x;
    while(tata[rad])
        rad=tata[rad];
    while(tata[x])
    {
        aux=tata[x];
        tata[x]=rad;
        x=aux;
    }

    return x;
}

void Union (int i, int j)
// il fac pe j fiu al lui i
// i si j sunt radacinile arborilor care reprezinta cele doua multimi
{
    if(h[i]<h[j])
    {
        tata[i]=j;
    }
    else
    {
        tata[j]=i;
        if(h[i]==h[j])
            ++h[i];
    }
}


/*void write_heap(int H[NMAX], int n)
{
int i;

for (i=1; i<=n; i++)
    fprintf(fout, "%d ", H[i]);
fprintf(fout, "\n");
}*/

void afisare()
{
    int i;
    fprintf(fout, "%d\n", cost);
    fprintf(fout, "%d\n", n-1);
    for(i=1; i<=n; ++i)
        fprintf(fout, "%d %d\n", G[A[i]].x, G[A[i]].y);
    fclose(fout);
}