#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){
    if(c[val] == val)
        return val;
    c[val] = findR(c[val]);
    return c[val];
}

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(findR(Muchii[i].x) != findR(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;
}