#include <bits/stdc++.h>
#define cin fin
#define cout fout
using namespace std;

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

vector <pair <int, int> > adj[200005];
bitset <200005> reached;

struct edge {
    int u, v, cost;

    edge(int u, int v, int cost) {
        this->u = u;
        this->v = v;
        this->cost = cost;
    }
};

struct comp {
    bool operator()(edge a, edge b) {
        return a.cost > b.cost;
    }
};

int main() {
    int n, m;

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, cost;

        cin >> u >> v >> cost;
        adj[u].push_back(make_pair(v, cost));
        adj[v].push_back(make_pair(u, cost));
    }

    priority_queue <edge, vector <edge>, comp> next;
    vector <edge> res;
    int total = 0;
    next.push(edge(1, 1, 0));
    while (!next.empty()) {
        auto curr = next.top();
        next.pop();

        if (reached[curr.v]) {
            continue;
        }

        if (curr.u != curr.v) {
            res.push_back(curr);
        }
        total += curr.cost;

        reached[curr.v] = 1;
        for (auto nextEdge : adj[curr.v]) {
            next.push(edge(curr.v, nextEdge.first, nextEdge.second));
        }
    }

    cout << total << '\n';
    cout << res.size() << '\n';
    for (auto curr : res) {
        cout << curr.u << ' ' << curr.v << '\n';
    }


    return 0;
}