/**
Kruskal - az osszefuggo komponenseket faban tarolva
Minden csomopontra el fogom tarolni, hogy ki a kozvetlen ose. Ez kezdetben mindenkinel 0 (vagy onmaga is lehet).
Ahogy a sima kruskalnal, itt is megyek vegig a berendezett eleken. Lekerdezem az el ket vegenek gyokeret.
Ha a gyoker kulonbozo, akkor kulonbozo komponensben vannak, vagyis ossze kell kotnom oket. Ekkor beallitom,
hogy az egyik gyoker kozvetlen ose a masik gyoker legyen.
Ha igy csinalom megeshet az, hogy egy nagyon hosszu lancon kell tobbszor vegigmenjek. Ezert azt csinalom, hogy
amikor mar visszafele jovok a gyokertol (mert rekurzivan mentem, szoval visszaterek ugyenabba a pontba), akkor
az adott pont kozvetlen oset atallitom a gyokerre, igy maskor, ha erre a pontra lepek szinte egybol megtalalom
a gyokeret.
**/

//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct adat
{
    int csp1,csp2,k;
};
vector<adat>x;

vector<long long>v; ///az tarolja a kozvetlen osoket

vector<pair<long long,long long> > meg; ///ebben van a megoldas

long long n,m,i,j,k,a,b,c,p,q,sum,db;

int has(adat a,adat b)
{
    return a.k<b.k;
    /*if(a.k>b.k) return 0;
    else return 1;*/
}

int leker(int csp)
{
    int l;
    if(v[csp]) l=leker(v[csp]); ///ha van ose belelepek
    else return csp;    ///ha nincs, akkor ez gyoker, szoval visszateritem, hogy a gyoker az adott csp

 //   v[csp]=l;   ///beallitom uj kozvetlen oskent a gyokeret
    return l;
}

int main()
{
    cin>>n>>m;
    x.resize(m+1);
    for(i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        x[i].csp1=a;
        x[i].csp2=b;
        x[i].k=c;
    }

    sort(x.begin()+1,x.end(),has);

    v.resize(n+1,0);
   // for(i=1;i<=n;++i)
   //     v[i]=i;

    for(i=1;i<=m;++i)
    {
        a=x[i].csp1;
        b=x[i].csp2;
        k=x[i].k;
        p=leker(a); ///az a gyokere
        q=leker(b); ///a b gyokere
        if(q!=p)    ///ha nem ugyanabban a komponensben vannak
        {
            sum+=k;
            /*for(j=1;j<=n;++j)
            if(v[j]==q) v[j]=p;*/
            v[p]=q; ///az egyik gyoker kozvetlen osenek beallitom a masik gyokeret, igy osszekotom a komponenseket
            db++;
            meg.push_back({a,b});
        }
        if(db==n-1) break;
    }
    cout<<sum<<"\n"<<meg.size()<<"\n";
    for(i=0;i<meg.size();++i)
        cout<<meg[i].first<<" "<<meg[i].second<<"\n";
    return 0;
}