#include <iostream>
#include <fstream>
using namespace std;
ifstream f("graf.in");
ofstream g("apm.out");
long m,n,*tata,*h;
struct muchie
{
    int e1,e2,c;
};
muchie *A,*Arb;
void citire()
{
    f>>n>>m;
    tata=new int[n+1];
    h=new int[n+1];
    A=new muchie[m+1];
    Arb=new muchie[n];
    int i;
    for(i=1;i<=m;i++)
       f>>A[i].e1>>A[i].e2>>A[i].c;
    f.close();
}
void make(long x)
{
    tata[x]=h[x]=0;
}
long find(long x) //cu compresie de cale
{
    long r=x,y=x,t;
    while(tata[r])
       r=tata[r];
    while(y!=r)
    {
        t=tata[y];
        tata[y]=r;
        y=t;
    }
    return r;
}
void Union(long x,long y) //cu ponderare
{
    if(h[x]>h[y])
       tata[y]=x;
    else
    {
        tata[x]=y;
        if(h[x]==h[y])
            ++h[y];
    }
}
void quick_sort(long st,long dr)
{
    long i=st,j=dr;
    muchie w,piv=A[(i+j)/2];
    do
    {
        while(A[i].c<piv.c)
           ++i;
        while(A[j].c>piv.c)
           --j;
        if(i<=j)
        {
            w=A[i];
            A[i]=A[j];
            A[j]=w;
            i++;
            j--;
        }
    }while(i<=j);
    if(i<dr)
       quick_sort(i,dr);
    if(st<j)
       quick_sort(st,j);
}
void kruskal()
{
    long x,y,i=1,m_sel=0,cost=0;
    muchie M;
    while(m_sel<n-1)
    {
        M=A[i++];
        x=find(M.e1);
        y=find(M.e2);
        if(x!=y)
        {
            Arb[++m_sel]=M;
            cost+=M.c;
            Union(x,y);
        }
    }
    g<<cost<<'\n';
	g<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
       g<<Arb[i].e1<<' '<<Arb[i].e2<<'\n';
    g.close();
}
int main()
{
    citire();
    long i;
    for(i=1;i<=n;i++)
       make(i);
    quick_sort(1,m);
    kruskal();
    return 0;
}