#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

ofstream g("apm.out");

struct muchie
{
    int x, y, c;
}u[400001];

int n, m, i, l[200001], muchii[200001], k;

void citire()
{
    scanf("%d %d", &n, &m);
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d", &u[i].x, &u[i].y, &u[i].c);
    }
}

void poz(int s, int d, int &m)
{
    int i = s, j = d, ii = 1, jj = 0, aux;
    while (i < j) {
        if (u[i].c > u[j].c) {
            u[0] = u[i];
            u[i] = u[j];
            u[j] = u[0];
            aux = ii;
            ii = jj;
            jj = aux;
        }
        i += ii;
        j -= jj;
    }
    m = i;
}

void qsort(int s, int d)
{
    int m;
    if (s < d) {
        poz(s, d, m);
        qsort(s, m - 1);
        qsort(m + 1, d);
    }
}

int kruskal()
{
    int i, ct = 0, j, nr1, nr2;
    for (i = 1;  i <= n; i++) {
        l[i] = i;
    }
    i = 1;
    while (k < n - 1) {
        nr1 = l[u[i].x];
        nr2 = l[u[i].y];
        if (nr1 != nr2) {
            k++;
            muchii[k] = i;
            ct += u[i].c;
            for (j = 1; j <= n; j++) {
                if (l[j] == nr2) {
                    l[j] = nr1;
                }
            }
        }
        i++;
    }
    return ct;
}

int main()
{
    freopen("apm.in", "r", stdin);
    citire();
    qsort(1, m);
    g << kruskal() << "\n";
    g << k << "\n";
    i = 1;
    while (muchii[i]) {
        g << u[muchii[i]].x << " " << u[muchii[i]].y << "\n";
        i++;
    }
    return 0;
}