#include <fstream>
#define NMAX 102
#define MMAX 5000
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout ("apm.out");

struct Muchie {int x,y,c;};
Muchie G[MMAX];
int n,m,cost;
int conex[NMAX];
int A[NMAX];///indiciimuchiilorselect in arbore
///comp conex din carefaceparte i
bool compar(Muchie a,Muchie b)
///true daca muchia a trb sa fie inainteaceleia b in vectorul sortat
{
    return a.c<b.c;
}

void afisare()
{
    int i;
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(i=1;i<n;i++)
        fout<<G[A[i]].y<<' '<<G[A[i]].x<<'\n';
    fout.close();
}
void sortare();
void kruskal()
{
    int cx,cy,i,j,nrsel;
    ///ord muchie crescator dupacost
    ///sortare();
    sort(G+1,G+m+1,compar);
    for(i=1;i<=n;i++) conex[i]=i;
    nrsel=0;
    i=1;
    while(nrsel<n-1)
    {
        if(conex[G[i].x]!=conex[G[i].y])///select
    {
        nrsel++;
        A[nrsel]=i;
        cost+=G[i].c;
        ///unificare componentele conexe ale extremitatilor
        cx=conex[G[i].x];
        cy=conex[G[i].y];
        for(j=1;j<=n;j++)
        {
            if(conex[j]==cy)conex[j]=cx;
        }
    }
    i++;
    }

}
void citire()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>G[i].x>>G[i].y>>G[i].c;
    }
}
int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}
void sortare()
{
    int schimb,i;
    Muchie aux;
    do
    {
        schimb=0;
        for(i=1;i<m;i++)
            if(G[i].c>G[i+1].c)
        {
            aux=G[i];
            G[i]=G[i+1];
            G[i+1]=aux;
            schimb=1;
        }
    }
    while(schimb);
}