/*#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int n, m, step, apm_sum;
bool used[200005];

class Edge {
public:
    int node1, node2, cost;
};

class MinHeap {
public:
    inline bool operator () (Edge a, Edge b) {
        return a.cost > b.cost;
    }
};

priority_queue <Edge, vector <Edge>, MinHeap> Heap;
vector <Edge> G[200005], apm_list;

inline void apm() {
    while(step < n - 1) {
        Edge top = Heap.top();
        Heap.pop();

        if(used[top.node2]) {
            continue;
        }

        apm_sum += top.cost;
        ++step;
        apm_list.push_back(top);
        used[top.node1] = true;
        used[top.node2] = true;

        for(auto nxt: G[top.node2]) {
            if(used[nxt.node2]) {
                continue;
            }

            Heap.push(nxt);
        }
    }
}

int main() {
    cin >> n >> m;

    for(int i = 1; i <= m; ++i) {
        int a, b, d;
        cin >> a >> b >> d;
        G[a].push_back({a, b, d});
        G[b].push_back({b, a, d});
    }

    used[1] = true;

    for(auto it: G[1]) {
        Heap.push(it);
    }

    apm();

    cout << apm_sum << '\n' << n - 1 << '\n';

    for(auto it: apm_list) {
        cout << it.node1 << ' ' << it.node2 << '\n';
    }

    return 0;
}
*/

#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int n, m, apm_sum, edg_used, father[200005];
bool used[200005];

class Edge {
public:
    int node1, node2, cost;
};

vector <Edge> apm_list;

Edge edg[400005];

inline bool EdgeSort(Edge a, Edge b) {
    return a.cost < b.cost;
}

int find_root(int node) {
    if(node == father[node]) {
        return node;
    }

    return father[node] = find_root(father[node]);
}

void apm() {
    sort(&edg[1], &edg[m + 1], EdgeSort);
    used[edg[1].node1] = true;
    used[edg[1].node2] = true;
    used[edg[2].node1] = true;
    used[edg[2].node2] = true;
    father[edg[1].node2] = edg[1].node1;
    father[edg[2].node2] = edg[2].node1;
    apm_list.push_back(edg[1]);
    apm_list.push_back(edg[2]);
    apm_sum = edg[1].cost + edg[2].cost;

    for(int i = 3; i <= m and edg_used < n - 3; ++i) {
        if(find_root(edg[i].node1) == find_root(edg[i].node2)) {
            continue;
        }

        if(used[edg[i].node1] and used[edg[i].node2]) {
            father[find_root(edg[i].node1)] = find_root(edg[i].node2);
        }
        else if(!used[edg[i].node2]) {
            father[edg[i].node2] = find_root(edg[i].node1);
        }
        else {
            father[edg[i].node1] = find_root(edg[i].node2);
        }

        apm_sum += edg[i].cost;
        ++edg_used;
        used[edg[i].node1] = true;
        used[edg[i].node2] = true;
        apm_list.push_back(edg[i]);
    }
}

int main() {
    cin >> n >> m;

    for(int i = 1; i <= m; ++i) {
        cin >> edg[i].node1 >> edg[i].node2 >> edg[i].cost;
    }

    for(int i = 1; i <= n; ++i) {
        father[i] = i;
    }

    apm();

    cout << apm_sum << '\n' << n - 1 << '\n';

    for(auto it: apm_list) {
        cout << it.node1 << ' ' << it.node2 << '\n';
    }

    return 0;
}