#include <stdio.h>

#include <vector>
#include <queue>

struct node {
    node()
    {
        value = parent = -1;
    }

    node(int v)
    {
        value = parent = v;
    }

    int value;
    int parent;
};

struct edge {
    edge(int _u, int _v, int _w)
    {
        u = _u;
        v = _v;
        w = _w;
    }

    bool operator<(const edge& e) const
    {
        return e.w < w;
    }

    int u, v, w;
};

std::priority_queue<edge> edges;
std::vector<edge> a;
node nodes[200000];
int cost;

int get_parent(int u)
{
    if (nodes[u].parent == u)
        return u;

    return get_parent(nodes[u].parent);
}

void set_union(int u, int v, int w)
{
    int p_u = get_parent(u);
    int p_v = get_parent(v);

    if (p_u == p_v)
        return;

    nodes[p_u].parent = p_v;
    a.push_back(edge(u, v, w));
    cost += w;
}

int main()
{
    int n, m;

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

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

    for (int i = 0; i < n; i++)
        nodes[i] = node(i);

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

        edges.push(edge(u - 1, v - 1, w));
    }

    while (edges.size()) {
       edge e = edges.top();

       set_union(e.u, e.v, e.w);

       edges.pop();
    }


    printf("%d\n%d\n", cost, a.size());
    for (int i = 0; i < a.size(); i++) 
        printf("%d %d\n", a[i].u + 1, a[i].v + 1);

    return 0;
}