#include <stdio.h>
#include <stdlib.h>

#define NMAX 200000
#define MMAX 400000

static struct edge {
    int u;
    int v;
    int w;
    int next;
} edges[2*MMAX+1];

static int adj[NMAX+1], mst[NMAX], parent[NMAX+1], rank[NMAX+1];

static int ecmp(const void *a, const void *b)
{
    const struct edge *e1 = (const struct edge *) a;
    const struct edge *e2 = (const struct edge *) b;

    return e1->w - e2->w;
}

static void make_set(int x)
{
    parent[x] = x;
    rank[x] = 0;
}

static int find(int x)
{
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }

    return parent[x];
}

static void opunion(int x, int y)
{
    int s_x, s_y;

    s_x = find(x);
    s_y = find(y);

    if (rank[s_x] < rank[s_y]) {
        parent[s_x] = s_y;
    } else {
        parent[s_y] = s_x;
        if (rank[s_y] == rank[s_x]) {
            rank[s_x]++;
        }
    }
}

int main(void)
{
    int i, n, m, u, v, w, cost, sol;

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d", &n, &m);

    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &u, &v, &w);

        edges[2*i].u = v;
        edges[2*i].v = u;
        edges[2*i].w = w;
        edges[2*i].next = adj[v];
        adj[v] = 2*i;

        edges[2*i+1].u = u;
        edges[2*i+1].v = v;
        edges[2*i+1].w = w;
        edges[2*i+1].next = adj[u];
        adj[u] = 2*i+1;
    }

    for (i = 1; i <= n; i++) {
        make_set(i);
    }

    qsort(edges, 2 * m, sizeof edges[0], ecmp);

    cost = sol = 0;

    for (i = 0; i < 2 * m; i++) {
        if (find(edges[i].u) != find(edges[i].v)) {
            cost += edges[i].w;
            mst[sol++] = i;

            opunion(edges[i].u, edges[i].v);
        }
    }

    printf("%d\n%d\n", cost, n - 1);

    for (i = 0; i < n - 1; i++) {
        printf("%d %d\n", edges[mst[i]].u, edges[mst[i]].v);
    }

    return 0;
}