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

using namespace std;

vector<pair <int,pair<int,int> > > v1;

vector<pair <int,pair<int,int> > > v2;

vector<pair<int,int> > grandPadre;

int elGrandPadre(int i){
    if(grandPadre[i].first==i)
        return i;
    grandPadre[i].first=elGrandPadre(grandPadre[i].first);
    return grandPadre[i].first;
}

void imprietenire(int i,int j){
    int a=elGrandPadre(i);
    int b=elGrandPadre(j);


    if(grandPadre[a].second>grandPadre[b].second){
        grandPadre[b].first=a;


    }else if(grandPadre[a].second<grandPadre[b].second){
        grandPadre[a].first=b;


    }else{


        grandPadre[a].first=b;
        grandPadre[b].second++;
    }
}


int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");

    int n,m,cost,x,y;
    int cT=0;
    f>>n>>m;


    for(int i=0;i<m;i++){
        f>>x>>y>>cost;

        v1.push_back(make_pair(cost,make_pair(x,y)));
    }
    grandPadre.push_back(make_pair(1000,1));
    for(int i=1;i<=n;i++){
        grandPadre.push_back(make_pair(i,1));
    }
    sort(v1.begin(),v1.end());

    ///*
    for(vector<pair<int,pair<int,int> > >::iterator it=v1.begin(); it<v1.end(); ++it){
        if(grandPadre[(*it).second.first].first!=grandPadre[(*it).second.second].first){
            imprietenire(grandPadre[(*it).second.first].first,grandPadre[(*it).second.second].first);
            cT+=(*it).first;
            v2.push_back(*it);
        }
    }
    cout<<cT<<'\n'<<n-1<<'\n';
    for(vector<pair<int,pair<int,int> > >::iterator it=v2.begin(); it<v2.end(); ++it){
        cout<<(*it).second.second<<" "<<(*it).second.first<<'\n';
    }
    //*/
    return 0;
}