#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
#define DIMMAX 2000001
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

vector<int> d; // minimum cost vector

int Parent(int i) { return i / 2; }
int Left(int i) { return 2 * i; }
int Right(int i) { return 2 * i + 1; }

void HeapUp(int h[], vector<int>& posInHeap, int i) {
    while (i > 1 && d[h[Parent(i)]] > d[h[i]]) {
        swap(posInHeap[h[i]], posInHeap[h[Parent(i)]]);
        swap(h[i], h[Parent(i)]);
        i = Parent(i);
    }
}

void MinHeapify(int h[], vector<int>& posInHeap, int i, int dim_heap) {
    int smallest = i;
    int l = Left(i);
    int r = Right(i);

    if (l <= dim_heap && d[h[l]] < d[h[smallest]])
        smallest = l;
    if (r <= dim_heap && d[h[r]] < d[h[smallest]])
        smallest = r;

    if (smallest != i) {
        swap(posInHeap[h[i]], posInHeap[h[smallest]]);
        swap(h[i], h[smallest]);
        MinHeapify(h, posInHeap, smallest, dim_heap);
    }
}

int HeapExtractMin(int h[], vector<int>& posInHeap, int& dim_heap) {
    if (dim_heap < 1)
        return -1;
    int minNode = h[1];
    h[1] = h[dim_heap];
    posInHeap[h[1]] = 1;
    dim_heap--;
    MinHeapify(h, posInHeap, 1, dim_heap);
    return minNode;
}

void BuildMinHeap(int h[], vector<int>& posInHeap, int dim_heap) {
    for (int i = dim_heap / 2; i >= 1; i--)
        MinHeapify(h, posInHeap, i, dim_heap);
}

vector<vector<pair<int, int>>> generare_lista_adiacenta(int varfuri, int muchii) {
    vector<vector<pair<int, int>>> lista(varfuri);
    int x, y, cost;
    for (int i = 0; i < muchii; i++) {
        fin >> x >> y >> cost;
        lista[x - 1].push_back({ y, cost });
        lista[y - 1].push_back({ x, cost });
    }
    return lista;
}

void Prim(int n, int m, int s, vector<vector<pair<int, int>>>& lista_adiacenta_cu_cost,
          vector<pair<int, int>>& muchii_apcm, long long& cost) {
    int h[n + 1];
    vector<int> posInHeap(n + 1);

    for (int i = 1; i <= n; i++) {
        h[i] = i;
        posInHeap[i] = i;
    }

    d.resize(n + 1, INT_MAX);
    vector<int> tata(n + 1, 0);
    d[s] = 0;
    int dim_heap = n;
    BuildMinHeap(h, posInHeap, dim_heap);

    vector<bool> inHeap(n + 1, true);

    while (dim_heap) {
        int u = HeapExtractMin(h, posInHeap, dim_heap);
        inHeap[u] = false;

        for (const auto& muchie : lista_adiacenta_cu_cost[u - 1]) {
            int v = muchie.first;
            int cost_muchie = muchie.second;

            if (inHeap[v] && cost_muchie < d[v]) {
                d[v] = cost_muchie;
                tata[v] = u;

                int i = posInHeap[v];
                HeapUp(h, posInHeap, i);
            }
        }
    }

    for (int i = 1; i <= n; i++)
        if (i != s)
            muchii_apcm.push_back({ i, tata[i] }), cost += d[i];
}

int main() {
    int n, m;
    fin >> n >> m;
    vector<vector<pair<int, int>>> lista_adiacenta_cu_cost = generare_lista_adiacenta(n, m);
    fin.close();

    vector<pair<int, int>> muchii_apcm;
    long long cost = 0;

    Prim(n, m, 1, lista_adiacenta_cu_cost, muchii_apcm, cost);

    fout << cost << '\n' << n - 1 << '\n';
    for (const auto& muchie : muchii_apcm)
        fout << muchie.first << " " << muchie.second << '\n';
    fout.close();
    return 0;
}