#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

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

#define nmax 200005

int h[nmax], tata[nmax];

struct edge {int x, y, c;};
vector <edge> v;

vector <pair <int, int> > sol;

void onion (int x, int y) {
    if (h[x] > h[y]) tata[y] = x;
    else tata[x] = y;
    if (h[x] == h[y]) h[y]++;
}

int find (int x) {
    int r = x;
    while (tata[r]) r = tata[r];
    int y = x, t;
    while (y != r) {
        t = tata[y];
        tata[y] = r;
        y = t;
    }
    return r;
}

inline bool cmp (edge a, edge b) {
    return a.c < b.c;
}

int main()
{
    int x, y, c, sum = 0;
    unsigned int i, n, m;
    edge tmp;
    vector <pair <int, int> > :: iterator it;

    fin >> n >> m;

    for (i = 1; i <= m; ++i) {
        fin >> tmp.x >> tmp.y >> tmp.c;
        v.push_back(tmp);
    }

    sort(v.begin(), v.end(), cmp);

    for (i = 0; i < v.size(); ++i) {
        x = v[i].x;
        y = v[i].y;
        c = v[i].c;
        int a = find(x), b = find(y);
        if (a != b) {
            sum += c;
            sol.push_back(make_pair(x, y));
            onion(a, b);
        }
    }
    fout << sum << "\n" << n - 1 << "\n";


    for (it = sol.begin(); it != sol.end(); ++it) {
        fout << (*it).first << " " << (*it).second << "\n";
    }


    return 0;
}