#include<stdio.h>
using namespace std;
const int N = 200005, M = 400005, INF = 1005;
int vf[2 * M], lst[N], urm[2 * M], h[N], poz[N], v[N], nrh, nrg, c[2 * M], pre[N];
void adauga (int x, int y, int cost)
{
    vf[++nrg] = y;
    c[nrg] = cost;
    urm[nrg] = lst[x];
    lst[x] = nrg;
}
void schimba (int p1, int 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 && v[h[p]] < v[h[p / 2]])
    {
        schimba (p, p / 2);
        p /= 2;
    }
}
void coboara (int p)
{
    int bun = p, fs = p * 2, fd = p * 2 + 1;
    if (fs <= nrh && v[h[fs]] < v[h[bun]])
        bun = fs;
    if (fd <= nrh && v[h[fd]] < v[h[bun]])
        bun = fd;
    if (bun != p)
    {
        schimba (bun, p);
        coboara (bun);
    }
}
void init (int n)
{
    int i;
    for (i = 1; i <= n; i++)
    {
        h[i] = i;
        poz[i] = i;
        v[i] = INF;
    }
    nrh = n;
}
int main ()
{
    FILE *in, *out;
    in = fopen ("apm.in", "r");
    out = fopen ("apm.out", "w");
    int n, m;
    fscanf (in, "%d%d", &n, &m);
    int i, x, y, cost;
    for (i = 1; i <= m; i++)
    {
        fscanf (in, "%d%d%d", &x, &y, &cost);
        adauga (x, y, cost);
        adauga (y, x, cost);
    }
    int p, s = 0;
    init (n);
    v[1] = 0;
    while (nrh > 0)
    {
        x = h[1];
        s += v[x];
        schimba (1, nrh--);
        poz[x] = -1;
        coboara (1);
        p = lst[x];
        while (p > 0)
        {
            y = vf[p];
            cost = c[p];
            if (cost < v[y] && poz[y] != -1)
            {
                v[y] = cost;
                urca (poz[y]);
                pre[y] = x;
            }
            p = urm[p];
        }
    }

 //   s = 0;
  //  for (i = 1; i <= n; i++)
   //     s += v[i];
    fprintf (out, "%d\n%d\n", s, n - 1);
    for (i = 2; i <= n; i++)
        fprintf (out, "%d %d\n", i, pre[i]);

    return 0;
}