// Prim's algorithm
// Made in Romania by Florin Haja

#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

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

const int nmax = 200005, f_mare = 1500000006;

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

struct cmp {
    bool operator() (const edge &x, const edge &y) {
        return x.c > y.c;
    }
};

bool viz[nmax];
int n, m, x, y, i, j, c, l;
vector<int> tmp;
vector<edge> ls[nmax];
priority_queue<edge,vector<edge>, cmp> Heap;
pair<int,int> fin[nmax];
int dist[nmax];
int sol, ns;

int main() {
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y >> c;

        ls[x].push_back({x,y,c});
        ls[y].push_back({y,x,c});
    }
    for (i = 1; i <= n; i++)
        dist[i] = f_mare;

    dist[1] = 0;
    Heap.push({0, 1, 0});

    while (Heap.empty() == 0) {
        x = Heap.top().x;                       // ia muchia de cost minim
        y = Heap.top().y;                       // din priority_queue
        c = Heap.top().c;
        Heap.pop();

        if (y != 1 && viz[y] == 0) {            // s-a gasit muchia minima din nodul x
            viz[y] = 1;
            sol += c;
            fin[++ns] = make_pair(x, y);
        }
        x = y;
        l = ls[x].size();
        for (i = 0; i < l; i++) {
            c = ls[x][i].c;
            y = ls[x][i].y;
            if (dist[y] > c && viz[y] == 0) {    // se poate adauga o muchie de cost mai mic
                dist[y] = c;
                Heap.push({x,y,c});

            }
        }
    }
    g << sol << '\n' << n-1 << '\n';
    for (i = 1; i < n; i++)
        g << fin[i].first << ' '<< fin[i].second <<'\n';
    return 0;
}