#include <cstdio>
#define NMAX 200001
#define MMAX 400001
// min-Heap
using namespace std;
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 combinare(int H[NMAX], int n, int i);
void creare_heap_combinare(int H[NMAX], int& n);
int extragemin(int H[NMAX], int &n);
void afisare();
void citire();
int Find (int);
void Union (int, int);
void afisare_heap(int H[NMAX], int n);

int main()
{
    int nr=0, cx, cy, mmin;
    citire();
    creare_heap_combinare(H, m);
    //afisare_heap(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 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;
}

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);
}

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];
        }
    return;
}

void citire()
{
    int i;
    FILE*fin=fopen ("apm.in", "r");
    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);
    fclose(fin);
    return;
}

void afisare()
{

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

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");
}