#include <fstream>
#include <utility>
#include <algorithm>
#include <vector>

#define merge 1

std::ifstream f("apm.in");
std::ofstream g("apm.out");

using namespace std;

pair< int,pair<int,int> > muchii[400001];

vector<int> arbori[200001];

int locatie[200001];

vector<pair<int,int> > v;

int n,m,sum,k;

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        f>>muchii[i].second.first>>muchii[i].second.second>>muchii[i].first;
    }
    sort(muchii+1,muchii+m+1);
    for(int i=1;i<=n;++i)
        {
            arbori[i].push_back(i);
            locatie[i]=i;
        }

    for(int i=1;i<=m && k<n-1;++i)
    {
        if(locatie[muchii[i].second.first]!=locatie[muchii[i].second.second])
        {
            if(locatie[muchii[i].second.first]<locatie[muchii[i].second.second])
            {

                for(int j=0;j<arbori[muchii[i].second.second].size();++j)
                {

                    locatie[arbori[muchii[i].second.second][j]]=locatie[muchii[i].second.first];
                    arbori[muchii[i].second.first].push_back(arbori[muchii[i].second.second][j]);

                }
            }
            else
            {
                for(int j=0;j<arbori[muchii[i].second.first].size();++j)
                {

                    locatie[arbori[muchii[i].second.first][j]]=locatie[muchii[i].second.second];
                    arbori[muchii[i].second.second].push_back(arbori[muchii[i].second.first][j]);

                }
            }
            v.push_back(make_pair(muchii[i].second.first,muchii[i].second.second));
            sum = sum + muchii[i].first;
            k++;
        }
    }
    g<<sum<<'\n';
    g<<v.size()<<'\n';
    for(int i=0;i<v.size();++i)
    {
        g<<v[i].first<<" "<<v[i].second<<'\n';
    }
    return 0;
}