#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax 100001
using namespace std;

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

vector< pair<int, pair<int,int>> > cost_muchie; // m.first == costul, m.second.first = x, m.second.second = y;
vector<pair<int,int>> sol;
int n, m, tata[Nmax], rang[Nmax];;

void init() {
    for (int i=0; i<n; i++) {
        tata[i] = i; // parintele
        rang[i] = 1; // dimensiunea arborelui (cati copii are in total) => initial fiecare nod reprez un arbore form doar din rad
    }
}

int find (int x)
{
    while (x!=tata[x]) {
        x = tata[x];
        find(x);
    }
    return x;
}

void uneste(int x, int y) // reuniune dupa rang <=> atasez arborelui mai mare pe cel mai mic
{
    x = find(x);
    y = find(y);

    if (rang[x] >= rang[y]) {
        tata[y] = x;
        rang[x] += rang[y];
    }
    else {
        tata[x] = y;
        rang[y] += rang[x];
    }
}


int Kruskal()
{
    int cost = 0;
    sort(cost_muchie.begin(), cost_muchie.end());
    for (auto muchie: cost_muchie)
    {
        if (find(muchie.second.first) != find(muchie.second.second))
        {
            // cout << "a intrat in if pt " << muchie.second.first << " " << muchie.second.second << "\n";
            sol.push_back(muchie.second);
            uneste(muchie.second.first, muchie.second.second);
            cost += muchie.first;
            // cout << "  => cost = " << cost << "\n";
        }
    }
    return cost;
}


int main()
{
    int x, y, cost;
    fin >> n >> m;

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

    init();

//    for (int i=0; i<cost_muchie.size(); i++){
//        cout << find(cost_muchie[i].second.first) << " ";
//    }
//    cout << "\n";

    fout << Kruskal() << "\n" << sol.size() << "\n";

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

    return 0;
}