#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#define N 200008

using namespace std;

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

int n;
vector<pair<int, int>> g[N];
vector<pair<int, pair<int, int>>> edges;
vector<pair<int, int>> sol;
int Daddy[N];

void Citire() {
    int m;
    int x, y, c;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> c;
        edges.push_back({c, {x, y}});
    }
}

int Find(int x) {
    if (Daddy[x] == 0) return x;
    return Daddy[x] = Find(Daddy[x]);
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    Daddy[x] = y;
}

int Kruskal() {
    sort(edges.begin(), edges.end());
    int m = n - 1;
    int s = 0;
    for (auto e: edges) {
        if (m == 0) break;

        int x = e.second.first;
        int y = e.second.second;

        if (Find(x) == Find(y)) continue;
        Union(x, y);
        s += e.first;
        sol.push_back({x, y});
        m--;
    }
    return s;
}

int main() {
    Citire();
    fout << Kruskal() << "\n";
    fout << sol.size() << "\n";
    for (auto e: sol) {
        fout << e.first << " " << e.second << "\n";
    }
    return 0;
}