/// https://www.infoarena.ro/problema/apm
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, costTotal;
int x[400001], y[400001], cost[400001], ord[400001];
int tt[200001], rang[200001];
vector<pair<int, int> > sol;

bool cmp(int i, int j) {
    return (cost[i] < cost[j]);
}

void readAndSet() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        x[i] = a;
        y[i] = b;
        cost[i] = c;
        ord[i] = i;
        tt[i] = i;
    }
    sort(ord + 1, ord + m + 1, cmp);
}

int comp(int i) {
    int r;
    for (r = i; r != tt[r]; r = tt[r]);

    for (; i != r; ) {
        int aux = tt[i];
        tt[i] = r;
        i = aux;
    }

    return r;
}

bool sameComponent(int i, int j) {
    return (comp(i) == comp(j));
}

void unite(int i, int j) {
    if (rang[i] > rang[j])
        tt[j] = i;
    else
        tt[i] = j;
    if (rang[i] == rang[j])
        rang[i]++;
}

void solve() {
    for (int i = 1; i <= m; i++) {
        int a = x[ord[i]], b = y[ord[i]], c = cost[ord[i]];
        if (!sameComponent(a, b)) {
            unite(comp(a), comp(b));
            costTotal += c;
            sol.push_back(make_pair(a, b));
        }
    }
}

void print() {
    fout << costTotal << '\n' << sol.size() << '\n';
    for (pair<int, int> p : sol)
        fout << p.first << ' ' << p.second << '\n';
}

int main() {
    readAndSet();
    solve();
    print();
    return 0;
}