#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];

int arbori[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]=i;

    for(int i=1;i<=m && k<n-1;++i)
    {
        if(arbori[muchii[i].second.first]!=arbori[muchii[i].second.second])
        {
            if(arbori[muchii[i].second.first]<arbori[muchii[i].second.second])
            {
                int val = arbori[muchii[i].second.second];
                for(int j=1;j<=n;++j)
                {
                    if(arbori[j]==val)
                        arbori[j] = arbori[muchii[i].second.first];
                }
            }
            else
            {
                int val = arbori[muchii[i].second.first];
                for(int j=1;j<=n;++j)
                {
                    if(arbori[j]==val)
                        arbori[j] = arbori[muchii[i].second.second];
                }
            }
            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;
}