#include <iostream>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
struct muchie{
    int x;
    int y;
    int c;
}v[200003],aux;
int c[200003];
struct solutie{
    int x1;
    int y1;
}sol[200003];
/*int pozitie(int st,int dr)
{
    muchie val=v[st];
    while(st<dr)
    {
        while(st<dr&&v[dr].c>=val.c)
            dr--;
        v[st]=v[dr];
        while(st<dr&&v[st].c<=val.c)
            st++;
        v[dr]=v[st];
    }
    v[st]=val;
    return st;
}
void quicksort(int st,int dr)
{
    int poz=pozitie(st,dr);
    if(st<poz-1)
        quicksort(st,poz-1);
    if(dr>poz+1)
        quicksort(poz+1,dr);
} */
void quicksort(int st,int dr)
{
    muchie m=v[st+(dr-st)/2];
    int i=st;
    int j=dr;
    do
    {
        while(i<dr&&v[i].c<m.c)
            i++;
        while(j>st&&v[j].c>m.c)
            j--;
        if(i<=j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            i++;
            j--;
        }
    }while(i<=j);
    if(i<dr) quicksort(i,dr);
    if(j>st) quicksort(st,j);
}
int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    quicksort(1,m);
    //kruskal
    for(i=1;i<=n;i++)
        c[i]=i;//fiecare nod il punem intrun arbore diferit
    int a,cost=0;
    int nr=0;
    i=1;
    while(nr<n-1)
    {
        if(c[v[i].x]!=c[v[i].y]) //daca nodurile fac parte din multimi diferite
        {
            nr++;
            sol[nr].x1=v[i].x; //adaugam la solutie muchia
            sol[nr].y1=v[i].y;
            cost=cost+v[i].c; //calculam costul
            a=c[v[i].y];
            for(int j=1;j<=n;j++) //schimbam toate elementele care fac parte din alta multime in multimea arborelui
                if(c[j]==a)
                    c[j]=c[v[i].x];
        }
        i++;
    }
    g<<cost<<"\n";
    g<<n-1<<"\n";
    for(i=1;i<=n-1;i++)
        g<<sol[i].x1<<" "<<sol[i].y1<<"\n";
    return 0;
}