// apm

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

#define NMax 200000
#define MMax 400000

struct leg {
    int x;
    int y;
    int c;
};

struct nod {
    int r;
    int s;
};

int n, m, nunite;
vector<leg> muchii, tree;
nod noduri[NMax + 3];

void read() {
    int x, y, c;
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> c;
        muchii.push_back({x, y, c});
    }
}

void init() {
    for (int i = 1; i <= n; ++i) noduri[i] = {i, 1};
    sort(muchii.begin(), muchii.end(), [](leg a, leg b){if (a.c < b.c) return 1; return 0;});
}

int findrad(int i) {
    if (noduri[i].r == i) return i;
    else {
        noduri[i].r = findrad(noduri[i].r);
        return noduri[i].r;
    }
}

void unite(int i, int j) {
    i = findrad(i);
    j = findrad(j);
    if (noduri[i].s >= noduri[j].s) {
        noduri[j].r = i;
        noduri[i].s += noduri[j].s;
    } else {
        noduri[i].r = j;
        noduri[j].s += noduri[i].s;
    }

    ++nunite;
}

void constructtree() {
    read();
    int i, j;
    for (auto a : muchii) {
        i = findrad(a.x);
        j = findrad(a.y);
        if (i != j) {
            tree.push_back(a);
            unite(i, j);
        }
        if (nunite >= n - 1) return;
    }
}

void output() {
    int s = 0;
    for (auto l : tree) s += l.c;
    fout << s << '\n' << n - 1 << '\n';
    for (auto l : tree) {
        fout << l.x << ' ' << l.y << '\n';
    }
}

int main()
{
    read();
    init();
    constructtree();
    output();
}