#include <cstdio>
#include <vector>
#include <algorithm>
#define NMAX 50001
using namespace std;
FILE *fin, *fout;
const int inf=1<<28;
struct lista {
    int vf, c;
}aux;
struct varf {
    int vf, c;
    bool operator< (varf &xx) { return c>xx.c; }
}auxh;
vector <lista> graf[NMAX];
vector <varf> heap;
int dist[NMAX], prec[NMAX], cost;
bool sel[NMAX];
int n, m;
int main()
{
    int i, a, b, c, vf, pus=1;
    fin=fopen("apm.in", "r"); fout=fopen("apm.out", "w");
    fscanf (fin, "%d%d", &n, &m);
    for (i=1; i<=m; ++i) { //citesc graf neorientat
        fscanf (fin, "%d%d%d", &a, &b, &c);
        aux.vf=b; aux.c=c; graf[a].push_back(aux);
        aux.vf=a; graf[b].push_back(aux);
    }
    for (i=1; i<=n; ++i) dist[i]=inf; dist[1]=0; sel[1]=1;
    for (i=0; i<graf[1].size(); ++i) {
        dist[graf[1][i].vf]=graf[1][i].c;
        prec[graf[1][i].vf]=1;
        auxh.c=graf[1][i].c; auxh.vf=graf[1][i].vf;
        heap.push_back(auxh);
    }
    make_heap(heap.begin(), heap.end());
    while (!heap.empty() && pus<n) {
        //scot varful din heap
        auxh=heap.front(); pop_heap(heap.begin(), heap.end()); heap.pop_back(); vf=auxh.vf;
        if (!sel[vf]) { sel[vf]=1; cost+=dist[vf]; ++pus; }
        //optimizez costurile adiacentilor
        for (i=0; i<graf[vf].size(); ++i) if (!sel[graf[vf][i].vf]) {
            if (graf[vf][i].c<dist[graf[vf][i].vf]) {
                //actualizez distanta si precedentul
                dist[graf[vf][i].vf]=graf[vf][i].c;
                prec[graf[vf][i].vf]=vf;
                //inserez varful in heap
                auxh.vf=graf[vf][i].vf; auxh.c=dist[graf[vf][i].vf];
                heap.push_back(auxh); push_heap(heap.begin(), heap.end());
            }
        }
    }
    fprintf (fout, "%d\n%d\n", cost, n-1);
    for (i=2; i<=n; ++i) fprintf (fout, "%d %d\n", i, prec[i]);
    fprintf (fout, "\n");
    fclose(fin); fclose(fout);
    return 0;
}