#include <fstream>
#include <algorithm>

#define NMAX 200010
#define MMAX 400010

using std::pop_heap;
using std::make_heap;

std::ifstream fin("apm.in");
std::ofstream fout("apm.out");

struct Edge {
    int x, y;
    int cost;
};

inline bool operator<(Edge x, Edge y) {
    return x.cost > y.cost;
}

int n, m;
Edge heap[MMAX];

int h[NMAX];
int father[NMAX];

int cost;
Edge sol[NMAX];

int find(int x) {
    int root = x;
    while (father[root])
        root = father[root];

    int aux;
    while (father[x]) {
        aux = father[x];
        father[x] = root;
        x = aux;
    }
    return root;
}

void unite(int x, int y) {
    int findX = find(x);
    int findY = find(y);

    if (h[findX] < h[findY])
        father[findX] = findY;
    else {
        father[findY] = findX;
        if (h[findX] == h[findY])
            h[findX]++;
    }
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++)
        fin >> heap[i].x >> heap[i].y >> heap[i].cost;

    make_heap(heap, heap + m);
    for (int i = 1; i < n; ) {
        Edge edge = heap[0];
        pop_heap(heap, heap + m);
        m--;

        if (find(edge.x) != find(edge.y)) {
            unite(edge.x, edge.y);
            cost += edge.cost;
            sol[i++] = edge;
        }
    }

    fout << cost << '\n' << n - 1 << '\n';
    for (int i = 1; i < n; i++)
        fout << sol[i].x << ' ' << sol[i].y << '\n';

    fout.close();
    return 0;
}