#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 200000;
const int MMAX = 400000;

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

int father[NMAX + 1];

struct edge{
    int x;
    int y;
    int cost;
    bool used;
};

edge edges[MMAX + 1];

// Return 1 is a < b, 0 otherwise
bool cmp(edge a, edge b) {
    return a.cost < b.cost;
}

int root(int x) {
    if (x == father[x])
        return x;
        
    int r = root(father[x]);
    father[x] = r;
    return r;
}

bool unite(int a, int b) {
    int x = root(a);
    int y = root(b);

    if (x == y) {
        return false;
    }

    father[x] = y;
    return true;
}

int main() {
    int n, m;

    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
    }
    
    for (int i = 1; i <= m; ++i) {
        fin >> edges[i].x;
        fin >> edges[i].y;
        fin >> edges[i].cost;
        edges[i].used = false;
    }

    sort(edges + 1, edges + m + 1, cmp);

    int sum = 0, k = n - 1;
    for (int i = 1; i <= m && k > 0; ++i) {
        if (unite(edges[i].x, edges[i].y)) {
            edges[i].used = true;
            sum += edges[i].cost;
            --k;
        }
    }

    fout << sum << "\n";
    fout << n - 1 << "\n";
    for (int i = 1; i <= m; ++i) {
        if (edges[i].used) {
            fout << edges[i].x << " " << edges[i].y << "\n";
        }
    }

    return 0;
}