#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <tuple>
#include <functional>
#define MAXN 200010
#define mktp make_tuple

using namespace std;

struct compare{
    bool operator() (const tuple<int, int, int> &a, const tuple<int, int, int> &b) {
        return (get<0>(a) > get<0>(b));
    }
};

priority_queue<tuple<int, int, int>, vector<tuple<int, int, int> >, compare > heap;
tuple<int, int, int> 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.push(mktp(it.second, 1, it.first));
    }
    while(k < nr) {
        int from, to, cost;
        tuple<int, int, int> temp = heap.top();
        from = get<1>(temp);
        to = get<2>(temp);
        cost = get<0>(temp);
        heap.pop();
        if (used[to] == false) {
            solutionCost += cost;
            used[to] = true;
            solution[k++] = mktp(cost, from, to);
            for (auto& it: edges[to]) {
                if (used[it.first] == false) {
                    heap.push(mktp(it.second, to, it.first));
                }
            }
        }
    }
}

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

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