#include <stdio.h>
#include <vector>
#include <queue>
#define NMAX 200001

using namespace std;

typedef struct {
    int x, y, cost;
} MUCHIE;

struct MinHeap {
    bool operator()(MUCHIE* &first, MUCHIE* &second) {
        return first->cost > second->cost;
    }
};

priority_queue< MUCHIE*, vector<MUCHIE*>, MinHeap > heap;
int n, m, viz[NMAX];
long long ans, nodes;
vector< pair<int, int> > graf[NMAX];
vector< pair<int, int> > result;

MUCHIE* makeMuchie(int x, int y, int c) {
    MUCHIE *m = new MUCHIE;
    m->x = x;
    m->y = y;
    m->cost = c;
    return m;
}

void prim() {
    MUCHIE *curr;
    viz[1] = nodes = 1;
    for(int i = 0; i < graf[1].size(); ++i)
        heap.push(makeMuchie(1, graf[1][i].first, graf[1][i].second));
    while(nodes != n) {
        curr = heap.top();
        heap.pop();
        while(viz[curr->y]) {
            curr = heap.top();
            heap.pop();
        }
        ans += curr->cost;
        result.push_back(make_pair(curr->x, curr->y));
        ++nodes;
        viz[curr->y] = 1;
        for(int i = 0; i < graf[curr->y].size(); ++i)
            heap.push(makeMuchie(curr->y, graf[curr->y][i].first, graf[curr->y][i].second));
    }
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int x, y, c;

    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; ++i) {
        scanf("%d%d%d", &x, &y, &c);
        graf[x].push_back(make_pair(y, c));
        graf[y].push_back(make_pair(x, c));
    }

    prim();

    printf("%lld\n", ans);
    printf("%d\n", n - 1);
    for(int i = 0; i < result.size(); ++i) {
        printf("%d %d\n", result[i].first, result[i].second);
    }

    return 0;
}