#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 200001
#define M 400001
#define INF (1 << 30)

typedef struct element element;

struct element
{
    int vf, urm, c;
};

int d[N], h[N], poz[N], nh, n, m, nr, pred[N], lst[N], cost;
bool selectat[N];
element e[2*M];

void schimba(int p1, int p2)
{
    ///schimba intre ele elem. de pe poz. p1 si p2
    int aux = h[p1];
    h[p1] = h[p2];
    h[p2] = aux;
    poz[h[p1]] = p1;
    poz[h[p2]] = p2;
}

void urca(int p)
{
    while (p > 1 && d[h[p]] < d[h[p/2]])///cat timp elem. curent e mai bun ca tatal sau
    {
        schimba(p, p/2);
        p /= 2;///continuam urcarea
    }
}

void adauga(int val)
{
    h[++nh] = val;///il pun la final pentru a avea arb. bin. complet
    poz[val] = nh;
    urca(nh);///pentru a pastra proprietatea de heap
}

void coboara(int p)
{
    ///daca h[p] e mai rau ca (cel putin) unul dintre fii
    ///il schimb cu cel mai bun dintre fii
    int fs = 2*p, fd = 2*p + 1, bun = p;
    if (fs <= nh && d[h[fs]] < d[h[bun]])///fiul stang exista si e mai bun ca tatal
    {
        bun = fs;
    }
    if (fd <= nh && d[h[fd]] < d[h[bun]])///fiul drept exista si e mai bun ca tatal
    {
        bun = fd;
    }
    if (bun != p)///unul dintre fii e mai bun ca tatal
    {
        schimba(p, bun);
        coboara(bun);///coboram in continuare pentru a reface heap-ul
    }
}

void sterge(int p)
{
    ///sterge elem. de pe pozitia p in heap
    if (p == nh)
    {
        nh--;
    }
    else
    {
        h[p] = h[nh--];
        poz[h[p]] = p;
        //schimba(p, nh--);
        urca(p);
        coboara(p);
    }
}

void adauga_e(int x, int y, int c)
{
    ///il adauga pe y in lista lui x cu costul c
    ++nr;
    e[nr].vf = y;
    e[nr].c = c;
    e[nr].urm = lst[x];
    lst[x] = nr;
}

void prim()
{
    int i;
    d[1] = 0;
    adauga(1);
    for (i = 2; i <= n; i++)
    {
        d[i] = INF;
        pred[i] = 0;
        adauga(i);
    }
    while (nh > 0)
    {
        int x = h[1];
        selectat[x] = true;
        sterge(1);
        cost += d[x];
        ///parcurg vecinii lui x si le actualizez distantele fata de apm
        int p = lst[x];
        while (p != 0)
        {
            int y = e[p].vf;
            int c = e[p].c;
            if (c < d[y] && !selectat[y])
            {
                pred[y] = x;
                d[y] = c;
                urca(poz[y]);
            }
            p = e[p].urm;
        }
    }
}

int main()
{
    FILE *in, *out;
    in = fopen("apm.in", "r");
    out = fopen("apm.out", "w");
    int i;
    fscanf(in, "%d%d", &n, &m);
    for (i = 0; i < m; i++)
    {
        int x, y, c;
        fscanf(in, "%d%d%d", &x, &y, &c);
        adauga_e(x, y, c);
        adauga_e(y, x, c);
    }
    prim();
    fprintf(out, "%d\n%d\n", cost, n - 1);
    for (i = 2; i <= n; i++)
    {
        fprintf(out, "%d %d\n", pred[i], i);
    }
    fclose(in);
    fclose(out);
    return 0;
}