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

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

const int N_MAX = 2e5 + 5;

struct Edges {
    int x, y, c;

    bool operator < (const Edges other) const {
        return c < other.c;
    }
};

int N, M;
int dad[N_MAX], rnk[N_MAX];

vector <Edges> edges, answer;

int root(int node) {
    if(node == dad[node])
        return node;
    return dad[node] = root(dad[node]);
}

void join(int x, int y) {
    x = root(x);
    y = root(y);

    if(rnk[x] == rnk[y]) {
        rnk[x] ++;
        dad[y] = x;
    }
    else
        if(rnk[x] > rnk[y])
            dad[y] = x;
        else
            dad[x] = y;
}


int main() {
    fin >> N >> M;

    for(int i = 1; i <= N; i++)
        dad[i] = i;

    for(int i = 1; i <= M; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        edges.push_back({x, y, c});
    }

    sort(edges.begin(), edges.end());

    long long APM = 0;

    for(auto it : edges) {
        if(root(it.x) != root(it.y)) {
            join(it.x, it.y);
            APM += it.c;
            answer.push_back(it);
        }
    }

    fout << APM << '\n' << N - 1 << '\n';
    for(auto it : answer)
        fout << it.x << ' ' << it.y << '\n';

    return 0;
}