/*
    Varianta KRUSKAL
*/


#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, x, y, c, suma, cost, tataX, tataY;
vector< pair< int, pair<int, int> > >  muchii;  //x -> y, cost c
vector< pair<int, int> > tata;                  //tata si rank(size)
vector< pair<int, int> > solutie;               //x -> y

bool comparator(pair< int, pair<int, int> > a, pair< int, pair<int, int> > b) {
    return a.second.second < b.second.second;
}

//gaseste in ce componenta conexa se afla nodul, ca sa nu avem cicluri
int find(int nod) {
    if(tata[nod].first != nod) 
        tata[nod].first = find(tata[nod].first);

    return tata[nod].first;
}

void unionn(int x, int y) {
    if( tata[x].second < tata[y].second ) 
        tata[x].first = y;
    else if( tata[x].second > tata[y].second )
        tata[y].first = x;
    else {
        tata[y].first = x;
        tata[x].second++;
    }
}

int main() {
    fin >> n >> m;
    
    tata.reserve(n + 1);
    for(int i = 1; i <= n; i++) 
        tata[i] = make_pair(i, 0);

    for(int i = 0; i < m; i++) {
        fin >> x >> y >> c;
        muchii.push_back(make_pair(x, make_pair(y, c)));
    }

    sort(muchii.begin(), muchii.end(), comparator);

    for(int i = 0; i < m; i++) {
        x = muchii[i].first;
        y = muchii[i].second.first;
        cost = muchii[i].second.second;

        tataX = find(x);
        tataY = find(y);

        if(tataX != tataY) {
            unionn(tataX, tataY);
            solutie.push_back(make_pair(x, y));
            suma += cost;
        }
    }

    fout << suma << '\n' << solutie.size() << '\n';

    for(int i = 0; i < solutie.size(); i++) 
        fout << solutie[i].first << " " << solutie[i].second << '\n';
    
    return 0;
}