#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

#define NMAX 200001
#define INFINIT 5000

#define tata(x) (x / 2)
#define fiuStanga(x) (2 * x)
#define fiuDreapta(x) (2 * x + 1)

vector< pair<int, short> > muchii[NMAX];
vector< pair<int, int> > raspuns;
int heap[NMAX];
int predecesori[NMAX];
int costuri[NMAX];
int pozitii[NMAX];
bitset<NMAX> vizitat;

int scoateDinHeap();
void adaugaInHeap(int x);
void percolate(int poz);
void sift(int poz);

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

    int n, m;
    fin >> n >> m;

    while (m--) {
        int x, y, c;
        fin >> x >> y >> c;
        muchii[x].push_back(make_pair(y, c));
        muchii[y].push_back(make_pair(x, c));
    }

    for (int i = 1; i <= n; ++i) {
        costuri[i] = INFINIT;
    }
    costuri[1] = 0;

    adaugaInHeap(1);

    int costArbore = 0;
    for (int i = 1; i <= n; ++i) {
        int curent = scoateDinHeap();
        vizitat[curent] = true;

        if (predecesori[curent] != 0) {
            raspuns.push_back(make_pair(predecesori[curent], curent));
            costArbore += costuri[curent];
        }

        for (auto muchie : muchii[curent]) {
            int vecin = muchie.first;
            if (!vizitat[vecin] && muchie.second < costuri[vecin]) {
                bool inHeap = (costuri[vecin] != INFINIT);
                costuri[vecin] = muchie.second;
                predecesori[vecin] = curent;
                if (inHeap)
                    percolate(pozitii[vecin]);
                else adaugaInHeap(vecin);
            }
        }
    }

    fout << costArbore << "\n" << n - 1 << "\n";
    for (auto muchie : raspuns) {
        fout << muchie.first << " " << muchie.second << "\n";
    }

    return 0;
}

int scoateDinHeap()
{
    int x = heap[1];

    swap(pozitii[heap[heap[0]]], pozitii[heap[1]]);
    swap(heap[1], heap[heap[0]]);
    --heap[0];
    sift(1);

    return x;
}

void adaugaInHeap(int x)
{
    heap[++heap[0]] = x;
    pozitii[x] = heap[0];
    percolate(heap[0]);
}

void percolate(int poz)
{
    while (poz != 1 && costuri[heap[poz]] < costuri[heap[tata(poz)]]) {
        swap(pozitii[heap[poz]], pozitii[heap[tata(poz)]]);
        swap(heap[poz], heap[tata(poz)]);
        poz = tata(poz);
    }
}

void sift(int poz)
{
    int fiu;
    do {
        fiu = 0;

        if (fiuStanga(poz) <= heap[0]) {
            fiu = fiuStanga(poz);
            if (fiuDreapta(poz) <= heap[0] && costuri[heap[fiuDreapta(poz)]] < costuri[heap[fiu]]) {
                fiu = fiuDreapta(poz);
            }

            if (costuri[heap[fiu]] < costuri[heap[poz]]) {
                swap(pozitii[heap[fiu]], pozitii[heap[poz]]);
                swap(heap[poz], heap[fiu]);
                poz = fiu;
            }
            else {
                fiu = 0;
            }
        }
    } while (fiu != 0);
}