#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;

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

// alte comments
// de data asta cu paduri de multimi disjuncte

int tatici[200002], rang[200002];

struct muchie {
    int x, y, cost;
} v[400005];

bool cmp(muchie a, muchie b) {
    return a.cost < b.cost;
}

// gasim radacina

int radacina(int k) {
    if(tatici[k] != k)
        tatici[k] = radacina(tatici[k]);
    return tatici[k];
}

// unim

void unire(int k, int p) {
    int rk = radacina(k), rp =radacina(p);
    if(rk == rp) return;
    if(rang[rk] < rang[rp]) swap(rk, rp);
    tatici[rp] = rk;
    if(rang[rp] == rang[rk]) rang[rk]++;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }

    sort(v + 1, v + 1 + m, cmp);
    vector<muchie> muchii;
    // initializare
    for(int i = 1; i <= n; i++) {
        tatici[i] = i;
        rang[i] = 0;
    }
    int total = 0;

    for(int i = 1; i <= m; i++) {
        // exact ca inainte, daca extremitatile sunt in subarbori diferiti
        if(radacina(v[i].x) != radacina(v[i].y)) {
            total += v[i].cost;
            muchii.push_back(v[i]);
            // aici unim doar o singura data
            // nu de fiecare data cum era dincolo
            unire(v[i].x, v[i].y);
        }
    }

    fout << total << '\n' << n - 1 << '\n';
    for(auto i : muchii) {
        fout << i.x << " " << i.y << '\n';
    }
    return 0;
}