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

vector< pair< int,pair<int,int> > > multime;
vector<pair<int,int> > muchie;
int n,m,t[200005],inaltime[200005],x,y,c,suma=0,nr=0;

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

void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        multime.push_back(make_pair(c,make_pair(x,y)));

    }
}

int gasire_radacina(int x)     //urcam pe pozitia radacinii
{
    if(t[x]==x)
        return x;
    else
        return t[x]=gasire_radacina(t[x]);

}

void reuniune(int x,int y)
{
    int a,b;
    a=gasire_radacina(x);   //pozitionam variabilele a si b pe pozitia radacinilor
    b=gasire_radacina(y);   //celor doi arbori

    if(inaltime[a]<inaltime[b])   //verificam care este arborele cu inaltimea mai mare
        t[a]=b;     //si il lipim pe cel mic de cel mare
    else
        t[b]=a;

    if(inaltime[a]==inaltime[b])  //daca inaltimile arborilor sunt egale atunci inaltimea o sa creasca cu 1
        ++inaltime[b];
}

int cmp( pair< int,pair<int,int> >  a, pair< int,pair<int,int> >b)
{
    if(a.first<b.first)
        return 1;
    return 0;
}

void Kruskal()
{
    citire();
    sort(multime.begin(),multime.end(),cmp);

    for(int i=1;i<=n;i++)
    {
        t[i]=i;
        inaltime[i]=0;
    }

    for(int i=0;i<m;i++)
    {
        int a;
        int b;
        a=multime[i].second.first;
        b=multime[i].second.second;
        if(gasire_radacina(a)!=gasire_radacina(b))
        {
            nr++;
            suma=suma+multime[i].first;
            reuniune(a,b);
            muchie.push_back(make_pair(b,a));
        }
    }

    g<<suma<<"\n"<<nr<<"\n";
    for(int i=0;i<nr;i++)
        g<<muchie[i].first<<" "<<muchie[i].second<<"\n";


}

int main()
{
    Kruskal();

    return 0;
}