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

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

using namespace std;

struct graf{
    int x, y, cost;
};

vector<graf> G;
vector<pair<int,int> > rasp;

bool comparare(graf a, graf b){
    return a.cost < b.cost;
}

int viz[200001];

int gr[200001];

int grup(int nod){
    if(gr[nod] == nod){
        return nod;
    }
    gr[nod] = grup(gr[nod]);

    return gr[nod];
}

void uneste(int nod1, int nod2) {
    gr[grup(nod1)] = grup(nod2);

}

int main()
{
    int N, M;
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        graf muchie;
        fin >> muchie.x >> muchie.y >> muchie.cost;
        G.push_back(muchie);
    }
    sort(G.begin(), G.end(), comparare);

    for (int i = 1; i <= N; i++){
        gr[i] = i;
    }

    int cost = 0;
    

    for (int i = 0; i < M; i++)
    {
        if(grup(G[i].x) != grup(G[i].y)){
            uneste(G[i].x, G[i].y);
            cost += G[i].cost;
            viz[i] = 1;
            rasp.push_back(make_pair(G[i].x, G[i].y));
        }
    }
    fout << cost << '\n';
    fout << N - 1 << '\n';
    for (int i = 0; i < rasp.size(); i++){
        fout << rasp[i].first << ' ' << rasp[i].second << '\n';
    }
}