#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 height[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 rootX, int rootY) {
    if (height[rootX] < height[rootY])
        father[rootX] = rootY;
    else {
        father[rootY] = rootX;
        if (height[rootX] == height[rootY])
            height[rootX]++;
    }
}

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--;

        int rootX = find(edge.x);
        int rootY = find(edge.y);

        if (rootX != rootY) {
            unite(rootX, rootY);
            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;
}