#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 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;

    rez.push_back(Muchii[1]);
    c[Muchii[1].x] = c[Muchii[1].y] = min(c[Muchii[1].x], c[Muchii[1].y]);
    int cost = Muchii[1].cost;
    int nrM = 1;
    for(int i = 2; i <= m && nrM < n - 1; ++i){
        if(c[Muchii[i].x] != c[Muchii[i].y]){
            rez.push_back(Muchii[i]);
            int minn = min(c[Muchii[i].x], c[Muchii[i].y]);
            int maxx = max(c[Muchii[i].x], c[Muchii[i].y]);
            for(int i = 1; i <= n; ++i)
                if(c[i] == maxx)
                    c[i] = minn;
            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;
}