#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

const int maxm = 4e5 + 5;
const int maxn = 2e5 + 5;
vector < pair<int,int> > Apm;
int Dad[maxn], Rang[maxn];

class Edges {
public:
    int x, y, cost;
    inline bool operator () (const Edges& A, const Edges& B) {
        return A.cost < B.cost;
    }
} V[maxm];

int Find(int x) {
    while (x != Dad[x]) {
        x = Dad[x];
    }
    return x;
}

void Union(int x, int y) {
    if (Rang[x] > Rang[y]) {
        Dad[y] = x;
    } else {
        Dad[x] = y;
    }
    if (Rang[x] == Rang[y]) {
        Rang[y]++;
    }
}

void Kruskal(int n, int m) {
    vector < pair <int,int> > :: iterator it;
    int rx, ry, i, minC = 0;
    sort(V + 1, V + m + 1, Edges());
    for (i = 1; i <= n; i ++) {
        Dad[i] = i;
    }
    for (i = 1; i <= m; i++) {
        rx = Find(V[i].x);
        ry = Find(V[i].y);
        if (rx != ry) {
            minC += V[i].cost;
            Union(rx, ry);
            Apm.push_back(make_pair(V[i].x, V[i].y));
        }
    }
    fout << minC << "\n" << n - 1 <<  "\n";
    for (it = Apm.begin(); it != Apm.end(); it++) {
        fout << it->first << " " << it->second << "\n";
    }
}

int main() {
    ios_base :: sync_with_stdio (false);
    int n, m, i;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> V[i].x >> V[i].y >> V[i].cost;
    }
    Kruskal(n, m);
    fin.close();
    fout.close();
    return 0;
}