#include <stdio.h>
#include <vector>
#include <utility>
#define M 400000
#define N 200000

struct muchie { int x, y, c; };
inline bool operator < (struct muchie a, struct muchie b) { return a.c < b.c; }

struct muchie muchii[M];
int parent[1 + N];
std::vector <std::pair<int, int>> ans;
int n, m;

void init(int n) {
    for ( int i = 1; i <= n; i ++ )
        parent[i] = i;
}

int getParent(int x) {
    if ( parent[x] == x )
        return x;
    return parent[x] = getParent(parent[x]);
}

void unite(int x, int y) {
    int px, py;

    px = getParent(x);
    py = getParent(y);

    parent[py] = px;
}

int main() {
    FILE *fin, *fout;

    fin = fopen("apm.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for ( int i = 0; i < m; i ++ )
        fscanf(fin, "%d%d%d", &muchii[i].x, &muchii[i].y, &muchii[i].c);
    fclose(fin);

    init(n);

    std::sort(muchii, muchii + m);

    int sum = 0;
    for ( int i = 0; i < m; i ++ ) {
        if ( getParent(muchii[i].x) != getParent(muchii[i].y) ) {
            unite(getParent(muchii[i].x), getParent(muchii[i].y));
            sum += muchii[i].c;
            ans.push_back(std::make_pair(muchii[i].x, muchii[i].y));
        }
    }

    fout = fopen("apm.out", "w");
    fprintf(fout, "%d\n%lu\n", sum, ans.size());
    for ( unsigned int i = 0; i < ans.size(); i ++ )
        fprintf(fout, "%d %d\n", ans[i].first, ans[i].second);
    fclose(fout);
    return 0;
}