#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, costTotal;
vector<pair<int, int> > nod[200001];
bitset<200001> inGraph;
priority_queue<pair<int, pair<int, int> > > c;
vector<pair<int, int> > sol;

void readAndSet() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        nod[a].push_back(make_pair(b, c));
        nod[b].push_back(make_pair(a, c));
    }
}

void prim() {
    c.push(make_pair(0, make_pair(1, 0)));
    while (!c.empty()) {
        int cost = -c.top().first;
        int i = c.top().second.first;
        int tata = c.top().second.second;
        c.pop();

        if (!inGraph[i]) {
            inGraph[i] = true;
            costTotal += cost;
            if (tata != 0)
                sol.push_back(make_pair(i, tata));

            for (pair<int, int> way : nod[i])
                if (!inGraph[way.first])
                    c.push(make_pair(-way.second, make_pair(way.first, i)));
        }
    }
}

void print() {
    fout << costTotal << '\n' << sol.size() << '\n';
    for (pair<int, int> p : sol)
        fout << p.first << ' ' << p.second << '\n';
}

int main() {
    readAndSet();
    prim();
    print();
    return 0;
}