#include <fstream>
#include <set>
#include <utility>
#include <vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int N,M,X,Y,C,g[200005],cost_total,nrgrup,marime[200005],nod1,nod2,cost;
struct much {int cc; int x; int y; bool friend operator <(much m1, much m2) {return (m1.cc<m2.cc || (m1.cc==m2.cc && m1.x<m2.x) || (m1.cc==m2.cc && m1.x==m2.x && m1.y<m2.y));}};
struct nodes{int n1; int n2;};
set <much> harta;
vector <nodes> sol;
int Find(int nod)
{
    int radacina=nod;
    ///Find
    while(g[radacina]!=radacina)
    {
        radacina=g[radacina];
    }
    ///Compresie
    while(nod!=radacina)
    {
        int next=g[nod];
        g[nod]=radacina;
        nod=next;
    }
    return radacina;
}
void Union(int nod1,int nod2)
{
    if(marime[nod1]>=marime[nod2])
    {
        g[Find(nod2)]=Find(nod1);
        marime[nod1]=marime[nod1]+marime[nod2];
    }
    else
    {
        g[Find(nod1)]=Find(nod2);
        marime[nod2]=marime[nod2]+marime[nod1];
    }
    nrgrup--;
}
void create_groups()
{
    for(int i=1; i<=N; i++)
    {
        g[i]=i;
        marime[i]=1;
    }
    nrgrup=N;
}
void citire()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        fin>>X>>Y>>C;
        much m={C,X,Y};
        harta.insert(m);
    }
}
int Kruskal()
{
    create_groups();
    for(set <much> :: iterator it= harta.begin(); it!=harta.end(); it++)
    {
        nod1=(*it).x;
        nod2=(*it).y;
        cost=(*it).cc;
        if(Find(nod1)!=Find(nod2))
        {
            Union(nod1,nod2);
            sol.push_back({nod1,nod2});
            cost_total=cost_total+cost;
        }
        if(nrgrup==1) return 0;
    }
    return 0;
}
void afis()
{
    fout<<cost_total<<'\n'<<N-1<<'\n';
    for(vector<nodes> :: iterator it = sol.begin(); it!=sol.end(); it++)
        fout<<(*it).n1<<' '<<(*it).n2<<'\n';

}
int main()
{
    citire();
    Kruskal();
    afis();
    return 0;
}