#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXM 400010
#define MAXN 200010

using namespace std;

struct element {
    int x, y, cost;
    bool operator<(const element &other) const {
        return (cost < other.cost);
    }
}edges[MAXM], solution[MAXN];

int n, m, maxNr, k = 0, father[MAXN], height[MAXN];
long long solCost = 0;

void initialize() {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
        height[i] = 1;
    }
}

void readInput() {
    ifstream fin("apm.in");
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, cost;
        fin >> x >> y >> cost;
        edges[i] = {x, y, cost};
    }
    maxNr = n - 1;
}

int doFather(int k) {
    if (k == father[k]) {
        return k;
    }
    father[k] = doFather(father[k]);;
}

void reunite(int x, int y) {
    father[x] = father[y];
    doFather(x);
    doFather(y);
    if (height[x] == height[y])
        height[x] = height[y] = height[x] + 1;
}

void solve() {
    for (int i = 0; k < maxNr; i++) {
        int x, y, cost;
        x = edges[i].x;
        y = edges[i].y;
        cost = edges[i].cost;
        doFather(x);
        doFather(y);
        if (father[x] != father[y]) {
            solCost += cost;
            reunite(x, y);
            solution[k++] = {x, y, cost};
        }
    }
}

void printSolution() {
    ofstream fout("apm.out");
    fout << solCost << "\n" << maxNr << "\n";
    for (int i = 0; i < maxNr; i++)
        fout << solution[i].x << " " << solution[i].y << "\n";
}

int main() {
    readInput();
    sort(edges, edges + m);
    initialize();
    solve();
    printSolution();
    return 0;
}