#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;
};
muchie G[NMAX];
int H[MMAX], A[NMAX], tata[NMAX], h[NMAX];
int n, m, cost;

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

int main()
{
int nr=0, cx, cy, mmin;

citire();
create_heap_combine(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;
}

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)
{
// il fac pe j fiu al lui i
// i si j sunt radacinilor arborilor care reprezinta
if (h[i]<h[j]) // i devine fiu al lui j
    tata[i]=j;
    else
    {
        tata[j]=i;
        if (h[i]==h[j])
            ++h[i];
    }
}

void combine(int H[MMAX], 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[MMAX], 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[MMAX], int &n)
{
int minim=H[1];
H[1]=H[n--];
combine(H, n, 1);
return minim;
}

void afisare()
{
int i;

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

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