#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, tata[200010], rang[200010], suma = 0;
vector<pair<int, int> > sol;

struct Iris {
    int x, y, val;
}v[400010];

inline int cmp(Iris a, Iris b) {
    return a.val < b.val;
}

int findTata(int nod) {
    while(tata[nod] != nod) nod = tata[nod];
    return nod;
}

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

int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++) fin >> v[i].x >> v[i].y >> v[i].val;
    sort(v+1, v+m+1, cmp);
    for(int i=1; i<=n; i++) tata[i] = i, rang[i] = 1;
    for(int i=1; i<=m; i++) {
        int tataX = findTata(v[i].x), tataY = findTata(v[i].y);
        if(tataX != tataY) { ///nu avem ciclu
            unireNoduri(tataX, tataY);
            suma += v[i].val;
            sol.push_back({v[i].x, v[i].y});
        }
    }
    fout << suma << '\n';
    fout << sol.size() << '\n';
    for(auto i : sol) fout << i.first << " " << i.second << '\n';

    return 0;
}