#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

struct muchie{
    int x, y, cost;
}Muchii[400005];
int c[200005];
vector<muchie> rez;

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

int findR(int val){
    int r = val;
    while(c[r] != r)
        r = c[r];
    return r;
}

void Unite(int val1, int val2){
    c[findR(val1)] = findR(val2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    int n, m;
    fin >> n >> m;

    for(int i = 1; i <= m; ++i)
        fin >> Muchii[i].x >> Muchii[i].y >> Muchii[i].cost;

    sort(Muchii + 1, Muchii + m + 1, cmp);

    for(int i = 1; i <= n; ++i)
        c[i] = i;

    int cost = 0;
    int nrM = 0;
    for(int i = 1; i <= m && nrM < n - 1; ++i){
        if(c[Muchii[i].x] != c[Muchii[i].y]){
            rez.push_back(Muchii[i]);
            Unite(Muchii[i].x, Muchii[i].y);
            cost += Muchii[i].cost;
            ++nrM;
        }
    }

    fout << cost << '\n';
    fout << rez.size() << '\n';
    for(int i = 0; i < rez.size(); ++i)
        fout << rez[i].x << ' ' << rez[i].y << '\n';
    return 0;
}