#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#define MAXN 200010

using namespace std;

struct edge{
    int x, y, cost;
    bool operator<(const edge &other) const {
        if (cost != other.cost)
            return (cost < other.cost);
        if (x != other.x)
            return (x < other.x);
        return (y < other.y);
    }
};

set<edge> heap;
edge solution[MAXN];
vector<pair<int, int> > edges[MAXN];
bool used[MAXN];
int n, m, nr, solutionCost = 0;

void readData() {
    ifstream fin("apm.in");
    int x, y, cost;
    fin >> n >> m;
    nr = n - 1;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> cost;
        edges[x].push_back(make_pair(y, cost));
        edges[y].push_back(make_pair(x, cost));
    }
}

void solve() {
    int k = 0;
    used[1] = true;
    for (auto& it: edges[1]) {
        if (used[it.first] == false)
            heap.insert({1, it.first, it.second});
    }
    while(k < nr) {
        int from, to, cost;
        from = heap.begin()->x;
        to = heap.begin()->y;
        cost = heap.begin()->cost;
        heap.erase(heap.begin());
        if (used[to] == false) {
            solutionCost += cost;
            used[to] = true;
            solution[k++] = {from, to, cost};
            for (auto& it: edges[to]) {
                if (used[it.first] == false) {
                    heap.insert({to, it.first, it.second});
                }
            }
        }
    }
}

void printSolution() {
    ofstream fout("apm.out");
    fout << solutionCost << "\n" << nr << "\n";
    for (int i = 0; i < nr; i++)
        fout << solution[i].x << " " << solution[i].y << "\n";
}

int main()
{
    readData();
    solve();
    printSolution();
    return 0;
}