#include <bits/stdc++.h>
#define pb push_back

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
const int MAXN = 200010;

struct Edge {
    int from, to, cost;
    bool operator<(const Edge& other) const {
        return cost < other.cost;
    }
}edges[2 * MAXN];
int fat[MAXN], dep[MAXN], n, m, k, cost, nr;
vector<pair<int, int> > sol;

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

int findFather(int node) {
    if (node == fat[node])
        return node;
    int f = findFather(fat[node]);
    fat[node] = f;
    return f;
}

void reunite(int x, int y) {
    if (dep[x] > dep[y])
        fat[y] = x;
    else
        fat[x] = y;
    if (dep[x] == dep[y])
        ++dep[y];
}

void read() {
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        edges[k++] = {x, y, c};
    }
}

void solve() {
    for (int i = 0; i < k && nr < m - 1; ++i) {
        int x = edges[i].from, y = edges[i].to, c = edges[i].cost, f1, f2;
        f1 = findFather(x);
        f2 = findFather(y);
        if (f1 != f2) {
            ++nr;
            sol.pb({x, y});
            cost += c;
            reunite(f1, f2);
        }
    }
}

void print() {
    fout << cost << '\n' << nr << '\n';
    for (const auto& it: sol)
        fout << it.first << ' ' << it.second << '\n';
}

int main() {
    read();
    initialize();
    sort(edges, edges + k);
    solve();
    print();
    return 0;
}