#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 pair <int, int> &a, const pair <int, int> &b) {
        return a.second > b.second;
    }
};

priority_queue <pair <int, int>, vector <pair <int, 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;
            heap.push(make_pair(it->first, it->second));
        }
    }
}

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

    cost[1] = 0;
    heap.push(make_pair(1, 0));

}

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);

    for (int i = 1; i <= n; ++i) {
        pair <int, int> top;
        while (viz[heap.top().first])
            heap.pop();

        top = heap.top();
        heap.pop();

        ans_cost += top.second;
        
        ans_edge.push_back(make_pair(top.first, father[top.first]));

        inApm(top.first);
    }

    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';

    return 0;
}