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

#define INT_MAX 2147483647

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


template <typename T>
class Heap {
public:
    T H[200000 + 1];
    int k = 0;

public:
    Heap() {}

    // utility
    void swap(int a, int b);
    int parent(int i);
    int left(int i);
    int right(int i);
    void heapUp(int i);
    void heapDown(int i);
    void insert(T x);
    T getMin();
    void del();
    int getSize() {
        return k;
    }
    void customDel(int i);
};

template <typename T>
int Heap<T>::parent(int i){
    return i / 2;
}

template <typename T>
int Heap<T>::left(int i){
    return 2 * i;
}

template <typename T>
int Heap<T>::right(int i){
    return 2 * i + 1;
}

template <typename T>
void Heap<T>::heapUp(int i){
    while (H[i] < H[this -> parent(i)] && i > 1){
        swap(i, this -> parent(i));
        i = this -> parent(i);
    }
}

template <typename T>
void Heap<T>::heapDown(int i){
    // while (true){
    //     int aux = i;
    //     if (this -> left(i) <= k){
    //         if (this -> right(i)<= k){
    //             if (H[this -> left(i)] < H[this -> right(i)])
    //                 if (H[this -> left(i)] > H[i])
    //                     swap(this -> left(i), i), i = this -> left(i);
    //             if (H[this -> right(i)] > H[i])
    //                 swap(this -> right(i), i), i = this -> right(i);
    //         }
    //         else if (H[this -> left(i)] > H[i])
    //             swap(this -> left(i), i), i = this -> left(i);
    //     }
    //     if (aux == i) 
    //         break;
    // }

    while(true) {
        int son = 0;
        if(left(i) <= k) {
            son = left(i);
            if(right(i) <= k && H[right(i)] < H[son]) {
                son = right(i);
            }
        }
        if(son && H[son] < H[i]) {
            swap(son, i);
            i = son;
        } else {
            break;
        }
    }
}

template <typename T>
void Heap<T>::insert(T x){
    H[++k] = x;
    this -> heapUp(k);
}

template <typename T>
T Heap<T>::getMin() {
    return H[1];
}

template <typename T>
void Heap<T>::swap(int a, int b){
    T aux = H[a];
    H[a] = H[b];
    H[b] = aux;
}

template <typename T>
void Heap<T>::del(){
    H[1] = H[k--];
    this -> heapDown(1);
}

template <typename T>
void Heap<T>::customDel(int i){
    if (H[k] < H[parent(i)]){
        H[i] = H[k--];
        this -> heapUp(i);
    }
    else{
        H[i] = H[k--];
        this -> heapDown(i);
    }
}

struct Muchie{
    int a, b, w;

    bool operator<(Muchie b){
        return this -> w < b.w;
    }
};

Heap<Muchie> dist;
vector<int> tata(200001, 0);
vector<bool> vizitat(200001, false);

int main(){
    int n, m, x, y, c;

    fin >> n >> m;

    int a[n + 1][n + 1];
    for (int i = 0; i <= n; ++i){
        for (int j = 0; j <= n; ++j){
            a[i][j] = INT_MAX;
        }
    }

    while(fin >> x >> y >> c){
        a[x][y] = a[y][x] = c;
    }

    int nodStart = 1;
    vizitat[nodStart] = true;

    for (int i = 1; i <= n; ++i){
        Muchie m;
        if (a[i][nodStart] < INT_MAX){
            m.a = nodStart;
            m.b = i;
            m.w = a[nodStart][i];
            dist.insert(m);

            tata[i] = nodStart;
        }
    }

    int costTotal = 0;
    vector<Muchie> rez;
    for (int k = 1; k <= n - 1; ++k){
        // selectam o muchie minima
        Muchie muchieMinima = dist.getMin();
        dist.del();
        if (vizitat[muchieMinima.b]) continue;
        vizitat[muchieMinima.b] = true;

        // cout << muchieMinima.a << " " << muchieMinima.b << endl;
        rez.push_back(muchieMinima);
        costTotal += muchieMinima.w;

        // adaugam noile muchii care pot fi considerate
        for (int i = 1; i <= n; ++i){
            Muchie m;
            // daca gasim o muchie mai buna pt un nod nevizitat care poate sa il lege la arbore, o adaugam
            if (!vizitat[i] && a[i][muchieMinima.b] < a[tata[i]][i]){
                m.a = muchieMinima.b;
                m.b = i;
                m.w = a[i][muchieMinima.b];

                // inlocuim alte muchii vechi
                for (int j = 1; j <= dist.k; ++j){
                    Muchie m = dist.H[j];
                    if (m.a == i && m.b == tata[i] || m.a == tata[i] && m.b == i){
                        dist.customDel(j);
                        break;
                    }
                }

                dist.insert(m);
                tata[i] = muchieMinima.b;
            }
        }

    }

    fout << costTotal << endl;
    fout << rez.size() << endl;
    for (Muchie m : rez){
        fout << m.a << " " << m.b << endl;
    }


}