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


using namespace std;

const int INF = 1 << 30;

ifstream f("apm.in");
ofstream g("apm.out");


class Graph {
private:
    int _n, _m;
    vector<vector<int>> _list;
    vector<vector<pair<int, int> >> _list2;

    int viz[200001] = {0};

public:
    Graph(int nodes, int edges) : _n(nodes), _m(edges) {}

    void add2();

    void apm_Prim(int node);
};


void Graph::add2() {
    int x, y, c;
    _list2.resize(_n + 1);

    for (int i = 0; i < _m; ++i) {
        f >> x >> y >> c;
        _list2[x].push_back(make_pair(y, c));
        _list2[y].push_back(make_pair(x, c));
    }
}


void Graph::apm_Prim(int start) {
    vector<pair<int, int>> ans;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    vector<int> costs(_n + 1, INF);
    vector<int> dad(_n + 1, 0);
    int total = 0;
    dad[start] = 0;
    costs[start] = 0;
    q.push(make_pair(0, start));

    while (!q.empty()) {
        int currentNode = q.top().second;
        q.pop();

        if (viz[currentNode] == 0) {
            viz[currentNode] = 1;

            for (int i = 0; i < _list2[currentNode].size(); ++i) {
                int neighbour = _list2[currentNode][i].first;
                int cost = _list2[currentNode][i].second;
                if (viz[neighbour] == 0 && cost < costs[neighbour]) {
                    costs[neighbour] = cost;
                    dad[neighbour] = currentNode;
                    q.push(make_pair(costs[neighbour], neighbour));
                }
            }
            total += costs[currentNode];
            if (dad[currentNode] != 0)
                ans.push_back(make_pair(currentNode, dad[currentNode]));
        }
    }

    g << total << '\n';
    g << ans.size() << '\n';
    for (int i = 0; i < ans.size(); ++i) {
        g << ans[i].first << " " << ans[i].second << '\n';
    }
}

int main() {
    int n, m;
    f >> n >> m;
    Graph gr(n, m);
    gr.add2();
    gr.apm_Prim(1);

    f.close();
    g.close();
    return 0;
}