#include <fstream>
#include <queue>
#include <climits>

using namespace std;

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

struct muchie{
    int start, dest, cost;
    muchie(int start, int destinatie, int cost){
        this->start = start;
        this->dest = destinatie;
        this->cost = cost;
    }
    bool operator<(const muchie &other) const {
        if(this->cost == other.cost)
            return this->dest > other.dest || this->start > other.start;
        return this->cost > other.cost;
    }
};

int n, m;
vector<muchie>graph[200005];
priority_queue<muchie> componenta;
bool vizitat[200005];

int costMin = INT_MAX, costMinInd = -1;
vector<muchie> comp;

int findComp(int begin){
    for (int i = 0; i < n; ++i) {
        vizitat[i] = false;
    }
    int nod = begin, cost = 0;
    for(auto i : graph[nod]){
        componenta.push(i);
    }
    vizitat[nod] = true;
    while(!componenta.empty()){
        if(vizitat[componenta.top().dest]){
            componenta.pop();
            continue;
        }
        comp.push_back(componenta.top());
        vizitat[componenta.top().start] = true;
        vizitat[componenta.top().dest] = true;
        cost += componenta.top().cost;
        nod = componenta.top().dest;
        componenta.pop();
        for(auto i : graph[nod]){
            componenta.push(i);
        }
    }
    return cost;
}

int main() {
    f>>n>>m;
    for (int i = 0; i < m; ++i) {
        int start, dest, cost;
        f>>start>>dest>>cost;
        graph[start - 1].emplace_back(start - 1, dest - 1, cost);
        graph[dest - 1].emplace_back(dest - 1, start - 1, cost);
    }
    int cost = INT_MAX;
    vector<muchie>rez;
    for(int i = 0; i < n; ++i, comp.clear()){
        int noua = findComp(i);
        if(noua < cost){
            rez = comp;
            cost = noua;
        }
    }
    g<<cost<<"\n"<<rez.size()<<"\n";
    for(auto &p : rez){
        g<<p.start + 1<<' '<<p.dest + 1<<"\n";
    }
    return 0;
}