//APM --------------------------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e5 + 5, mmax = 4e5 + 5;

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

int n, m, x, y, c, T[nmax], Rang[nmax], total, muchii;

typedef struct poz2{
    int a, b;
}student2;
vector < student2 > laturi;

typedef struct poz{
    int a, b, cost;
}student;
student v[mmax];

bool compare(student x, student y){
    if(x.cost < y.cost){
        return 1;
    }
    return 0;
}


int Radacina(int x){
    
    if(T[x] == x){
        return x;
    }else{
        int k = Radacina(T[x]);
        T[x] = k;
        return k;
    }
    
}

void Unire(int x, int y){
    x = Radacina(x) , y = Radacina(y);
    
    if(Rang[x] > Rang[y]){
        T[y] = x;
        Rang[x] += Rang[y];
    }else{
        T[x] = y;
        Rang[y] += Rang[x];
    }
    
}



int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>v[i].a>>v[i].b>>v[i].cost;
    }
    
    for(int i=1;i<=n;i++){
        T[i] = i;
        Rang[i] = 1;
    }
    
    sort(v+1 , v+m+1 , compare);
    
    for(int i=1;i<=m;i++){
        if(Radacina(v[i].a) != Radacina(v[i].b)){
            Unire(v[i].a , v[i].b);
            total += v[i].cost;
            muchii ++;
            laturi.push_back({v[i].a , v[i].b});
        }
    }
    
    fout<<total<<"\n"<<muchii<<"\n";
    for(int i=0;i<muchii;i++){
        fout<<laturi[i].a<<" "<<laturi[i].b<<"\n";
    }
    
}