//Algoritmul lui Prim

#define MAX_N 200001
#define INF 0x7fffffff
#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

struct structAdiacenta {
    int from;
    int to;
    int cost;
};

typedef vector<structAdiacenta> adiacente_t;
adiacente_t adiacente[MAX_N];
bool viz[MAX_N];
int n, m;
class comparare {
    public:
    bool operator() (const structAdiacenta &a, const structAdiacenta &b);
};


// heap-ul marcheaza lista de muchii adiacente, din care se selecteaza urmatorul nod.
priority_queue<structAdiacenta, std::vector<structAdiacenta>, comparare> heap;

int rezultatTotal;
adiacente_t rezultat;


void prim(int);

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

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++) {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        structAdiacenta structX;
        structX.from = x;
        structX.to = y;
        structX.cost = c;
        adiacente[x].push_back(structX);

        structAdiacenta structY;
        structY.from = y;
        structY.to = x;
        structY.cost = c;
        adiacente[y].push_back(structY);

    }

    prim(1);

    printf("%d\n", rezultatTotal);
    printf("%d\n", rezultat.size());
    for (adiacente_t::const_iterator i = rezultat.begin(); i != rezultat.end(); ++i) {
        printf("%d %d\n", i->from, i->to);
    }

    return 0;
}

#pragma mark - Heap

bool comparare::operator() (const structAdiacenta &a, const structAdiacenta &b) {
    return a.cost > b.cost;
}

#pragma mark - Algoritmul lui Prim

void prim(int start) {

    viz[start] = true;

    for (adiacente_t::const_iterator i = adiacente[start].begin(); i != adiacente[start].end(); ++i) {
        heap.push(*i);
    }

    while (!heap.empty()) {
        structAdiacenta top = heap.top();
        heap.pop();

        if (viz[top.to])
            continue;
        rezultatTotal += top.cost;
        rezultat.push_back(top);


        viz[top.to] = true;

        for (adiacente_t::const_iterator i = adiacente[top.to].begin(); i != adiacente[top.to].end(); ++i) {
            if (!viz[i->to]) {
                heap.push(*i);
            }
        }

    }


}