#include <stdio.h>
#include <stdlib.h>
#include <limits.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];
static int parent[NMAX+1], rank[NMAX+1];

static struct heap_elem {
    int node;
    int edge;
    int key;
} heap[NMAX+1];
static int node_to_heap_idx[NMAX+1], heap_size;

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]++;
        }
    }
}

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 insert(struct heap_elem x)
{
    int new_idx;
    struct heap_elem aux;

    heap_size++;

    heap[heap_size] = x;

    new_idx = heap_size;
    while (new_idx > 1 && heap[new_idx].key < heap[new_idx / 2].key) {
        aux = heap[new_idx];
        heap[new_idx] = heap[new_idx / 2];
        heap[new_idx / 2] = aux;

        node_to_heap_idx[heap[new_idx].node] = new_idx;

        new_idx /= 2;
    }

    node_to_heap_idx[x.node] = new_idx;
}

static void update(struct heap_elem x)
{
    int new_idx;
    struct heap_elem aux;

    new_idx = node_to_heap_idx[x.node];
    heap[new_idx] = x;

    while (new_idx > 1 && heap[new_idx].key < heap[new_idx / 2].key) {
        aux = heap[new_idx];
        heap[new_idx] = heap[new_idx / 2];
        heap[new_idx / 2] = aux;

        node_to_heap_idx[heap[new_idx].node] = new_idx;

        new_idx /= 2;
    }

    node_to_heap_idx[x.node] = new_idx;
}

static struct heap_elem extract_min(void)
{
    struct heap_elem x = heap[1], aux;
    int new_idx, aux_idx;

    heap[1] = heap[heap_size];
    node_to_heap_idx[x.node] = -1;
    heap_size--;

    new_idx = 1;
    while (new_idx * 2 < heap_size) {
        aux_idx = new_idx * 2;
        if (heap[aux_idx + 1].key < heap[aux_idx].key) {
            aux_idx++;
        }

        aux = heap[new_idx];
        heap[new_idx] = heap[aux_idx];
        heap[aux_idx] = aux;

        node_to_heap_idx[heap[new_idx].node] = new_idx;
        node_to_heap_idx[heap[aux_idx].node] = aux_idx;

        new_idx = aux_idx;
    }

    return x;
}

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

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

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

    for (i = 1; 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);
    }
    */

    for (i = 1; i <= n; i++) {
        x.node = i;
        x.key = i == 1 ? 0 : INT_MAX;

        insert(x);
    }

    sol = cost = 0;

    while (heap_size > 0) {
        x = extract_min();
        mst[sol++] = x.edge;
        cost += x.key;

        for (i = adj[x.node]; i != 0; i = edges[i].next) {
            if (node_to_heap_idx[edges[i].v] != -1 &&
                    edges[i].w < heap[node_to_heap_idx[edges[i].v]].key) {
                x.node = edges[i].v;
                x.key = edges[i].w;
                x.edge = i;
                update(x);
            }
        }
    }

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

    return 0;
}