#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#define mp make_pair
#define ft first
#define sd second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

vector<unsigned> father;
vector<unsigned> height;

unsigned getRoot(unsigned node){
    unsigned root = node, y;
    while(father[root] != root)
        root = father[root];
    while(node != root){
        y = father[node];
        father[node] = root;
        node = y;
    }
    return root;
}

void Union(unsigned x, unsigned y){
    unsigned rx = getRoot(x);
    unsigned ry = getRoot(y);
    if(height[rx] > height[ry])
        father[ry] = rx;
    else if(height[rx] < height[ry])
        father[rx] = ry;
    else {
        father[rx] = ry;
        height[ry]++;
    }
}

int main(){
    unsigned n, m, i, x, y;
    int c, total_cost = 0, selected = 0;
    priority_queue<pair<int, pair<unsigned, unsigned> > > edges;
    fin>>n>>m;
    for(i=1; i<=m; i++){
        fin>>x>>y>>c;
        edges.push(mp(-c, mp(x, y)));
    }

    father.resize(n+1);
    for(i=1; i<=n; i++)
        father[i] = i;
    height.assign(n+1, 0);

    vector<pair<unsigned, unsigned> > apm;
    vector<pair<unsigned, unsigned> > :: iterator it;
    pair<int, pair<unsigned, unsigned> > current;
    while(!edges.empty() && selected < n-1){
        current = edges.top();
        edges.pop();
        if(getRoot(current.sd.ft) != getRoot(current.sd.sd)){
            selected++;
            total_cost -= current.ft;
            Union(current.sd.ft, current.sd.sd);
            apm.push_back(mp(current.sd.ft, current.sd.sd));
        }
    }

    fout<<total_cost<<endl<<n-1<<endl;
    for(it = apm.begin(); it != apm.end(); it++)
        fout<<(*it).ft<<" "<<(*it).sd<<endl;
    return 0;
}