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

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

const int NMAX = 200000;
int n, m;

struct edge {
    int node, to, cost, id;
};
std::vector<edge> g[NMAX + 1];

bool in_apm[NMAX + 1];

void read() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        fin >> u >> v >> c;
        g[u].push_back(edge {u, v, c, i});
        g[v].push_back(edge {v, u, c, i});
    }
}

struct cmp {
    bool operator() (const edge & l, const edge & r) const {
        return l.cost > r.cost;
    }
};

std::priority_queue<edge, std::vector<edge>, cmp> pq;

void add(int node) {
    in_apm[node] = true;
    for (const edge & e : g[node])
        if (!in_apm[e.to])
            pq.push(e);
}

std::vector<std::pair<int, int>> ans;

void solve() {
    add(1);

    int total_cost = 0;

    for (int i = 1; i < n; i++) {
        while (in_apm[pq.top().node] && in_apm[pq.top().to])
            pq.pop();
        edge t = pq.top();
        pq.pop();
        total_cost += t.cost;
        ans.push_back(std::make_pair(t.node, t.to));
        add(t.to);
    }

    fout << total_cost << '\n';
    fout << n - 1 << '\n';
    for (const auto & it : ans) {
        fout << it.first << ' ' << it.second << '\n';
    }
}


int main() {
    read();
    solve();
    return 0;
}