#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int Nmax=400000;
struct muchie
{
    int x,y,c;
}aux;
muchie v[Nmax+5];
muchie sol[(Nmax>>1)+5];
void pozitie(int p,int u,int &k)
{
    int i,j,di,dj,aux1;
    i=p;
    di=0;
    j=u;
    dj=-1;
    while(i<j)
    {
        if(v[i].c>v[j].c)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            aux1=di;
            di=-dj;
            dj=-aux1;
        }
        i=i+di;
        j=j+dj;
    }
    k=i;
}
void quick(int p,int u)
{
    int k;
    if(p<u)
    {
        pozitie(p,u,k);
        quick(p,k-1);
        quick(k+1,u);
    }
}
int main()
{
    int arb[(Nmax>>1)+5]= {0},n,m;
    fin>>n>>m;
    int nr=0;
    while(m--)
    {
        nr++;
        fin>>v[nr].x>>v[nr].y>>v[nr].c;
    }
   quick(1,nr);
    //for(int i=1; i<=nr; i++)
    // cout<<v[i].x<<" "<<v[i].y<<" "<<v[i].c<<"\n";
    for(int i=1; i<=n; i++)
        arb[i]=i;
    int nrsel=0;
    int  k=1,cost=0;
    do
    {
        // if(nrsel==n-1)break;
        if(arb[v[k].x]!=arb[v[k].y])
        {
            int c,b;
            nrsel++;
            cost+=v[k].c;
            sol[nrsel].x=v[k].x;
            sol[nrsel].y=v[k].y;
            c=max(arb[v[k].x],arb[v[k].y]);
            b=min(arb[v[k].x],arb[v[k].y]);
            for(int j=1; j<=n; j++)
                if(arb[j]==b)
                    arb[j]=c;
        }
        k++;
    }
    while(nrsel!=n-1);
    fout<<cost<<"\n"<<nrsel<<"\n";
    for(int i=1; i<=nrsel; i++)
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";
}