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

using namespace std;

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

const int NMAX = 200005;
int dad[NMAX], rang[NMAX];
int n, m;
struct Muchie{
    int x, y, c;
};

vector < Muchie > muchii;
vector < Muchie > muchii_arb;

void read(){
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        Muchie mc;
        fin >> mc.x >> mc.y >> mc.c;
        muchii.push_back(mc);
    }
}

int Find(int nod){
    if(nod != dad[nod]){
        int repr = Find(dad[nod]);
        dad[nod] = repr; /// compresia -> complexitate
        return repr;
    }
    return nod;
}

void Union(int x, int y){
    if(rang[x] < rang[y]){
        dad[x] = y;
    }else if(rang[x] > rang[y]){
        dad[y] = x;
    }else{
        dad[x] = y;
        rang[y]++;
    }
}

int main()
{
    read();
    for(int i = 1; i <= n; i++){
        dad[i] = i;
    }
    /// sort(muchii + 1, muchii + M + 1)
    sort(muchii.begin(), muchii.end(),
         [](Muchie m1, Muchie m2){
            return m1.c < m2.c;
         });

    /**
    for(Muchie m: muchii){
        cout << m.x << " " << m.y << " " << m.c << "\n";
    }*/

    int sum_cost = 0;
    int muchii_tot = 0;
    for(int i = 0; i < muchii.size(); i++){
        int x = muchii[i].x;
        int y = muchii[i].y;
        int c = muchii[i].c;
        int repr_x = Find(x);
        int repr_y = Find(y);
        if(repr_x != repr_y){
            muchii_arb.push_back(muchii[i]);
            sum_cost += c;
            muchii_tot++;
            Union(repr_x, repr_y);
        }
    }

    fout << sum_cost << "\n";
    if(muchii_arb.size() != n - 1 && muchii_tot != n-1){
        cout << "NU-I OK!";
    }
    fout << n - 1 << "\n";
    for(auto muchie: muchii_arb){
        fout << muchie.x << " " << muchie.y << "\n";
    }
    return 0;
}