#include <fstream>
#include <algorithm>
using namespace std;

const int MAX_N = 200002;
const int MAX_M = 400002;

typedef struct edge {
    int x, y, c;
};

int N, M, ans;
int p[MAX_N], H[MAX_N];
edge v[MAX_M], sol[MAX_N];

inline int find(int x) {
    int R = x;
    while(R != p[R])
        R = p[R];
    while(x != p[x]) {
        int temp = p[x];
        p[x] = R;
        x = temp;
    }
    return R;
}

inline void unite(int x, int y) {
    if(H[x] > H[y])
        p[y] = x;
    else p[x] = y;
    if(H[x] == H[y])
        ++H[y];
}

inline bool cmp(edge a, edge b) {
    return a.c < b.c;
}

int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");

    f >> N >> M;
    for(int i = 1; i <= M; ++i)
        f >> v[i].x >> v[i].y >> v[i].c;

    for(int i = 1; i <= N; ++i)
        p[i] = i, H[i] = 1;
    sort(v+1, v+M+1, cmp);
    for(int i = 1, k = 1; k < N; ++i)
        if(find(v[i].x) != find(v[i].y)) {
            ans += v[i].c;
            unite(find(v[i].x), find(v[i].y));
            sol[k] = v[i], ++k;
        }

    g << ans << '\n' << N-1 << '\n';
    for(int i = 1; i < N; ++i)
        g << sol[i].x << " " << sol[i].y << '\n';

    f.close();
    g.close();

    return 0;
}