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

using namespace std;

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

#define FORIT(it, v) for (typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)

struct EDGES {
    int x, y, c;
};


const int N = 200005;
const int INF = 0x3f3f3f3f;

int n, m, ans_cost, pus;
int cost[N], father[N];
bool viz[N];
vector <pair <int, int> > graph[N], ans_edge;

struct cmp {
    bool operator () (const int &a, const int &b) {
        return cost[a] > cost[b];
    }
};

priority_queue <int, vector <int>, cmp > heap;

void inApm(int top) {
    viz[top] = true;
    FORIT(it, graph[top]) {
        if (!viz[it->first] && it->second < cost[it->first]) {
            father[it->first] = top;
            cost[it->first] = it->second;
        }
    }
}

void init(int n) {
    for (int i = 1; i <= n; ++i)
        cost[i] = INF;

    cost[1] = 0;

    for (int i = 1; i <= n; ++i)
        heap.push(i);
}

int main() {
    f >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        f >> x >> y >> c;
        graph[x].push_back(make_pair(y, c));
        graph[y].push_back(make_pair(x, c));
    }

    init(n);

    while (!heap.empty()) {
        int top;
        while (!heap.empty() && viz[heap.top()]) {
            heap.pop();
        }
        if (heap.empty())
            break;

        top = heap.top();
        inApm(top);
        ans_cost += cost[top];
        ans_edge.push_back(make_pair(top, father[top]));
        //heap.top();
        //inApm(top);
    }

    g << ans_cost << '\n';
    g << ans_edge.size() - 1 << '\n';
    for (int i = 1; i < ans_edge.size(); ++i)
        g << ans_edge[i].first << ' ' << ans_edge[i].second << '\n';
}