#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#define NMAX 200009
#define MMAX 400009
#define oo (1<<30)
using namespace std;
struct edge {
    int x,c;
    edge() {}

    edge(int _x, int _c) : x(_x), c(_c) {
    }

    bool operator()(const edge &a, const edge &b) const {
         return a.c > b.c;
    }
};


priority_queue<edge, vector<edge>, edge> pq;


int V, E, P[NMAX], cost, D[NMAX], root;
bitset<NMAX> used;
vector<edge> G[NMAX];

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

    scanf("%d%d", &V, &E);

    for (int i = 0; i < E; ++i) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);

        G[x].push_back( edge(y, c) );
        G[y].push_back( edge(x, c) );
    }


    for (int i = 1; i <= V; ++i) {
        D[i] = oo;
    }

    root = 1;

    D[root] = 0;
    pq.push( edge(root, 0) );

    for (int i = 1; i <= V; ++i) {
        while (used[ pq.top().x ]) {
            pq.pop();
        }
        int node = pq.top().x;
        pq.pop();
        cost += D[node];
        used[node] = 1;

        for (auto e = G[node].begin(); e != G[node].end(); ++e) {
            int son = e->x;
            int c = e->c;
            if (!used[son] && c < D[son]) {
                P[son] = node;
                D[son] = c;
                pq.push( edge(son, c ) );
            }
        }
    }

    printf("%d\n%d\n", cost, V - 1);

    for (int i = 1; i <= V; ++i) {
        if (i != root) {
            printf("%d %d\n", i, P[i]);
        }
    }
    return 0;

}