#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 200005
using namespace std;
FILE *fin, *fout;
struct muchie { int xx, yy, c; bool operator< (muchie aux) { return c>aux.c; } }aux;
vector <muchie> graf;
vector <muchie> apm;
int c[NMAX];
int n, m, cost=0;
int main()
{
    int i, j, mn, mx, sel;
    fin=fopen("apm.in", "r"); fout=fopen("apm.out", "w");
    fscanf (fin, "%d%d", &n, &m);
    for (i=1; i<=m; ++i) { fscanf (fin, "%d%d%d", &aux.xx, &aux.yy, &aux.c); graf.push_back(aux); }
    make_heap(graf.begin(), graf.end()); sel=1;
    for (i=1; i<=n; ++i) c[i]=i;
    while (sel<n) {
        aux=graf.front(); pop_heap(graf.begin(), graf.end()); graf.pop_back();
        if (c[aux.xx]!=c[aux.yy]) { //pot introduce muchia in arbore
            ++sel; cost+=aux.c;
            apm.push_back(aux);
            //unific cele doua componente conexe - comp mai mare in comp mai mica
            if (c[aux.xx]<c[aux.yy]) { mn=c[aux.xx]; mx=c[aux.yy]; }
            else { mn=c[aux.yy]; mx=c[aux.xx]; }
            for (j=1; j<=n; ++j) if (c[j]==mx) c[j]=mn;

        }
    }
    fprintf (fout, "%d\n%d\n", cost, n-1); --sel; for (i=0; i<sel; ++i) fprintf (fout, "%d %d\n", apm[i].xx, apm[i].yy);
    fclose(fin); fclose(fout);
    return 0;
}