#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 Muchie
{
    int x, y, c;
};
struct Muchie G[MMAX];

int H[MMAX];
int tata[NMAX];
int h[NMAX];//h[i] = inaltimea arborelui cu radacina i
int n, m;
long long int cost;
int A[NMAX];//retin indicii muchiilor selectate in APM

void citire();
void combinare(int H[NMAX], int n, int i);
void creare_heap_combinare(int H[NMAX], int& n);
int extragemin(int H[NMAX], int &n);
int Find (int);
void Union (int, int);
void afisare_heap(int H[NMAX], int n);
void afisare();

int main()
{
    int nr=0, cx, cy, mmin;
    citire();
    creare_heap_combinare(H, m);

    //kruskal
    while(nr<n-1)
    {
        mmin=extragemin (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, &m);
    for (i=1; i<=m; ++i)
        fscanf (fin, "%d %d %d", &G[i].x, &G[i].y, &G[i].c);
    return;
}

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

void combinare(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;
}

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

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

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

void afisare_heap(int H[NMAX], int n)
{
    int i;

    for (i=1; i<=n; i++)
        fprintf(fout, "%d %d %d\n", G[H[i]].x, G[H[i]].y, G[H[i]].c);
    fprintf(fout, "\n");
    fprintf(fout, "\n");
}

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