#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

struct forest{
    int tata;
    int inaltime;
}conexitate[200001];

void make_set( int x )
{
    conexitate[x].tata = x;
}

int find_set ( int x )
{
    if ( x != conexitate[x].tata )
        conexitate[x].tata = find_set( conexitate[x].tata );
    return conexitate[x].tata;
}

void link ( int x, int y )
{
    if ( conexitate[x].inaltime > conexitate[y].inaltime )
        conexitate[y].tata = x;
    else
        if( conexitate[x].inaltime < conexitate[y].inaltime )
            conexitate[x].tata = y;
        else{
            conexitate[y].tata = x;
            conexitate[x].inaltime++;
        }
}

void unite ( int x, int y )
{
    link( find_set(x), find_set(y) );
}

#include <vector>

vector < pair <int, pair<int, int> > > muchii;
vector < pair <int, pair<int, int> > > acp;

int main()
{
    int n, m;
    fin>>n>>m;
    int i;
    for(i=1; i<=m; i++)
    {
        int a, b, c;
        fin>>a>>b>>c;
        muchii.push_back({ c, {a, b} });
    }

    ///sorteaza
    sort(muchii.begin(), muchii.end(), less <pair <int, pair<int, int> > >()); //!se sorteazsa descrescator | cu less as fi sortat crescator

    //for(i=0; i<m; i++)
        //cout<<muchii[i].second.first<< " "<<muchii[i].second.second<<" "<<muchii[i].first<<endl;


    ///initializare
    for( i = 1; i <= n; i++ ) {
        make_set(i);
    }
    int nr_muchii_selectate=0;
    int cost_total=0;
    for(auto muchie: muchii)
    {
        //cout<<nr_muchii_selectate<<endl;
        //cout<< muchie.second.first<<" "<<muchie.second.second<<endl;
        int x = muchie.second.first;
        int y = muchie.second.second;
        if (find_set(x) != find_set(y))  ///reprezentanti
        {
            acp.push_back(muchie);
            cost_total += muchie.first;
            nr_muchii_selectate++;
            ///reuneste
            unite(x, y);
            if(nr_muchii_selectate == n-1)
            {
                //cout<<"bla";
                break;
            }
        }
    }

    fout<<cost_total<<'\n';
    fout<<acp.size()<<'\n';
    for(i=0; i<acp.size(); i++)
        fout<<acp[i].second.first<< " "<<acp[i].second.second<<'\n';
        //cout<<acp[i].second.first<< " "<<acp[i].second.second<<" "<<acp[i].first<<endl;


    fin.close();
    fout.close();
    return 0;
}