#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <list>

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

//ifstream fin("..\\grafpond.in");
//ofstream fout("..\\grafpond.out");
const int inf = 10000;

int n, m;
set<pair<int, int> > q;
///      cost  tag
vector<list<pair<int, int> > > graph;
///              cost tag
/// lista de adiacenta a grafului
vector<bool> viz;
vector<int> d;
vector<int> pred;
vector<pair<int, int> > E; /// apcm
int count;
int start;
int cost;

void read() {
    fin >> n >> m;

    graph.resize(n + 1);
    viz.resize(n + 1);
    d.resize(n + 1, inf);
    pred.resize(n + 1, inf);
    E.resize(m);

    for (int i = 0; i < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        graph[x].push_back(make_pair(c, y));
        graph[y].push_back(make_pair(c, x));
    }
    /*
    for (int i = 1; i <= n; i++) {
        cout << i << ": ";
        for (pair<int, int> p : graph[i])
            cout << "(" << p.first << ", " << p.second << "), ";
        cout << "\n";
    }*/
}

void prim() {
    start = 1;
    d[start] = 0;
    pred[start] = 0;
    q.insert(make_pair(d[start], start));

    while (!q.empty()) {
        pair<int, int> nod = *q.begin();
        q.erase(q.begin());
        if (viz[nod.second] == false) {
            viz[nod.second] = true;
            if (pred[nod.second]) {
                cost += nod.first;
                E[count].first = nod.second;
                E[count++].second = pred[nod.second];
            }
            for (auto i : graph[nod.second])
                if (viz[i.second] == false) {
                    if (d[i.second] > nod.first) {
                        pred[i.second] = nod.second;
                        d[i.second] = i.first;
                        q.insert(i);
                    }
                }
        }
    }
    fout << cost << "\n";
    fout << count << "\n";
    for (int i = 0; i < count; i++)
        fout << E[i].first << " " << E[i].second << "\n";
}

int main() {
    read();
    prim();

    return 0;
}