#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int arbore[200001];
pair<int,int>rezultat[200001];
pair<int, pair<int,int> > muchii[400001];
int n,m,cost_total,radacina1,radacina2,k;
int gaseste_radacina( int nod ){
    if( arbore[nod] < 0 ){
        return nod;
    }
    else{
        return gaseste_radacina( arbore[nod] );
    }
}
int main(){
    in >> n >> m;
    for( int i = 1; i <= m; i ++ ){
        in >> muchii[i].second.first >> muchii[i].second.second >> muchii[i].first;
    }
    for( int i = 1; i <= n; i ++ ){
        arbore[i] = -1;
    }
    sort( muchii + 1, muchii + m + 1 );
    for( int i = 1; i <= m; i ++ ){
        radacina1 = gaseste_radacina( muchii[i].second.first );
        radacina2 = gaseste_radacina( muchii[i].second.second );
        if( radacina1 == radacina2 ){
            continue;
        }
        else{
            if( arbore[radacina1] < arbore[radacina2] ){
                arbore[radacina1] += arbore[radacina2];
                arbore[radacina2] = radacina1;
            }
            else{
                arbore[radacina2] += arbore[radacina1];
                arbore[radacina1] = radacina2;
            }
            cost_total += muchii[i].first;
            rezultat[++k].first = muchii[i].second.first;
            rezultat[k].second = muchii[i].second.second;
        }
    }
    out<<cost_total<<"\n"<<n-1<<"\n";
    for( int i = 1; i <= n-1; i ++ ){
        out << rezultat[i].second <<" " << rezultat[i].first<< "\n";
    }
    return 0;
}