#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>

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

int main(){
    int n, m, nodStart = 1;
    fin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(n + 1));
    vector<bool> vizitat(200001, false);
    vector<int> tata(200001, 0);
    vector<pair<int, int>> rez;

    int x, y, w;
    for (int i = 1; i <= n; ++i){       // initializam cu costuri infinite
        for (int j = 1; j <= n; ++j){
            a[i][j] = INT_MAX;
        }
    }

    while (fin >> x >> y >> w){     // citim matricea de adiacenta
        a[x][y] = a[y][x] = w;
    }

    vizitat[nodStart] = true;

    // vectorul tata este un vector de potentiali tati in arbore care este updatat astfel incat
    // distanta intre 2 noduri tata-fiu sa fie minima
    for (int i = 1; i <= n; ++i){
        tata[i] = nodStart;         // marcam in arbore nodul de start ca fiind tatal tuturor
                                    // este ok pt ca o sa verificam ca distanta dintre aceste noduri sa nu fie infinita
    }
    tata[nodStart] = 0;

    int costTotal = 0;
    for (int k = 0; k < n - 1; ++k){    // alegem n - 1 muchii
        // vom alege un nod cu distanta minima care se poate lega la arborele deja format
        int distMin = INT_MAX;
        int nodMin;
        for (int i = 1; i <= n; ++i){
            if (!vizitat[i] && a[i][tata[i]] < distMin){
                distMin = a[i][tata[i]];
                nodMin = i;
            }
        }
        vizitat[nodMin] = true; // nodMin a fost selectat sa fie adaugat
        costTotal += a[nodMin][tata[nodMin]];

        pair<int, int> muchie;
        muchie.first = nodMin;
        muchie.second = tata[nodMin];
        rez.push_back(muchie);

        // updatam potentialii tati in functie de nodul adaugat la arbore
        // daca pt un nod exista un tata cu dist mai mica, il alegem
        for (int i = 1; i <= n; ++i){
            if (!vizitat[i] && a[i][tata[i]] > a[i][nodMin]){
                tata[i] = nodMin;
            }
        }

    }

    fout << costTotal << endl;
    fout << rez.size() << endl;
    for (pair<int, int> muchie : rez){
        fout << muchie.first << " " << muchie.second << endl;
    }
}