#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

const int NMAX = 400005;

ifstream cin("apm.in");
ofstream cout("apm.out");

int n, m, nr;
int cost_minim;

pair<pair<int, int>, int> Muchii[NMAX];
pair<int, int> Rezultat[NMAX];
map<int, int> parinte;
map<int, int> rang;

bool compare(const pair<pair<int, int> , int>& x, const pair<pair<int, int>, int>& y) {
    return x.second < y.second;
}


int cauta_parinte(int nod) {
    if (parinte[nod] == nod) return nod;
    return parinte[nod] = cauta_parinte(parinte[nod]);
}

void adauga(int x, int y) {
    if (rang[x] < rang[y]) parinte[x] = y;
    else if (rang[x] > rang[y]) parinte[y] = x;
    else if (rang[x] == rang[y]) parinte[x] = y, rang[y]++;
}

void kruskal() {
    for (int i = 1; i <= m; i++) {
        int tata_x = cauta_parinte(Muchii[i].first.first);
        int tata_y = cauta_parinte(Muchii[i].first.second);
        if (tata_x != tata_y) {
            adauga(tata_x, tata_y);
            Rezultat[++nr].first = Muchii[i].first.first;
            Rezultat[nr].second = Muchii[i].first.second;
            cost_minim += Muchii[i].second;
        }
    }
}


int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> Muchii[i].first.first >> Muchii[i].first.second >> Muchii[i].second;
    }
    sort(Muchii+1, Muchii + m+1, compare);
    for(int i=1;i<=m;i++){
        parinte[i]=i;
        rang[i]=1;
    }
    kruskal();
    cout<<cost_minim<<"\n";
    cout<<nr<<"\n";
    for(int i=1;i<=nr;i++,cout<<"\n") cout<<Rezultat[i].first<<" "<<Rezultat[i].second;
    return 0;
}