#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 200001

typedef pair<int, pair<int, int>> ElementCoada;

vector< pair<int, int> > muchii[NMAX];
vector< pair<int, int> > arbore;
vector<bool> inArbore(NMAX);

bool comp(ElementCoada a, ElementCoada b) {
    return a.first > b.first;
}

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

    int n, m;
    fin >> n >> m;

    while (m--) {
        int x, y, c;
        fin >> x >> y >> c;
        muchii[x].push_back({y, c});
        muchii[y].push_back({x, c});
    }

    priority_queue<ElementCoada, vector<ElementCoada>, decltype(&comp)> q(&comp);
    q.push({0, {0, 1}});

    int costArbore = 0;

    for (int i = 1; i <= n; ++i) {
        ElementCoada muchie;
        do {
            muchie = q.top();
            q.pop();
        } while (inArbore[muchie.second.second]);

        costArbore += muchie.first;
        if (muchie.second.second != 1)
            arbore.push_back(muchie.second);

        int curent = muchie.second.second;
        inArbore[curent] = true;

        for (auto v : muchii[curent]) {
            if (!inArbore[v.first]) {
                q.push({v.second, {curent, v.first}});
            }
        }
    }

    fout << costArbore << "\n" << n - 1 << "\n";
    for (auto muchie : arbore) {
        fout << muchie.first << " " << muchie.second << "\n";
    }

    return 0;
}