#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;
}