#include <fstream>
#include <algorithm>
#define NMAX 200000
#define MMAX 400000
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct Muchie{
    int e1, e2, cost;
}V[MMAX];

int n, m, nr, Suma;
int TT[NMAX], RG[NMAX], C[NMAX];

bool compare(Muchie a, Muchie b){
    return a.cost < b.cost;
}

void citire(){
    cin>>n>>m;
    for(int i=1; i<=m; i++)
        cin>>V[i].e1>>V[i].e2>>V[i].cost;

    sort(V + 1, V + m + 1, compare);

    for(int i=1; i<=n; i++){
        TT[i] = i;
        RG[i] = 1;
    }

}

int Find(int nod){
    while(TT[nod] != nod)
        nod = TT[nod];
    return nod;
}

void Unite(int x, int y){
    if(RG[x] < RG[y])
        TT[x] = y;
    else if(RG[x] > RG[y])
        TT[y] = x;
    else{
        TT[x] = y;
        RG[y]++;
    }

}

void Rezolvare(){
    for(int i=1; i<=m and nr<n-1; i++){
        int tata_x = Find(V[i].e1);
        int tata_y = Find(V[i].e2);

        if(tata_x != tata_y){
            Unite(tata_x, tata_y);
            C[++nr] = i;
            Suma+=V[i].cost;
        }

    }

}

int main(){
    citire();
    Rezolvare();

    cout<<Suma<<'\n'<<n-1<<'\n';

    for(int i=1; i<=n-1; i++)
        cout<<V[C[i]].e1<<' '<<V[C[i]].e2<<'\n';


    return 0;
}