#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m;
struct muchii
{
    int nod1, nod2;
    int cost;
    bool operator <(const muchii& other)const
    {
        return cost<other.cost;
    }
};
vector <muchii> v;
vector <muchii> rasp;
int tata[200500], lung_max[200500];
int cost_final, nr_muchii;
int radacina(int i)
{
    if(tata[i]==i)
    {
        return i;
    }
    return tata[i]=radacina(tata[i]);
}
void unire(int x, int y)
{
    int rad_x=radacina(x);
    int rad_y=radacina(y);
    if(lung_max[rad_x]>lung_max[rad_y])
    {
        tata[rad_y]=rad_x;
    }
    else if(lung_max[rad_x]<lung_max[rad_y])
    {
        tata[rad_x]=rad_y;
    }
    else
    {
        tata[rad_y]=rad_x;
        lung_max[rad_x]+=1;
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        muchii nou;
        fin>>nou.nod1>>nou.nod2>>nou.cost;
        v.push_back(nou);
    }
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
    {
        tata[i]=i;
    }
    for(int i=0;i<v.size();i++)
    {
        //cout<<tata[v[i].nod1]<<' '<<tata[v[i].nod2]<<' '<<v[i].cost<<'\n';
        if(radacina(v[i].nod1)!=radacina(v[i].nod2))
        {
            cost_final+=v[i].cost;
            nr_muchii++;
            rasp.push_back(v[i]);
            unire(v[i].nod1,v[i].nod2);
        }
    }
    fout<<cost_final<<'\n';
    fout<<nr_muchii<<'\n';
    for(int i=0;i<rasp.size();i++)
    {
        fout<<rasp[i].nod1<<' '<<rasp[i].nod2<<'\n';
    }
    return 0;
}