#include <fstream>
#include <algorithm>
#define NMAX 102
#define MMAX 1001

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

struct Muchie
{
    int x, y, c;
};
Muchie G[NMAX];
int conex[NMAX]; //conez[i]=comp conex din care face parte i
int n, m, minn, maxx, cost;
int A[NMAX]; //indicii muchiilor select in arbore

void citire();
void sortare();
void kruskal();
void afisare();
bool compar(Muchie a, Muchie b);
///returneaza 1 daca muchia a trebuie sa fie inaintea muchiei b in vect sortat
int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}
void citire()
{
    int i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        fin>>G[i].x>>G[i].y>>G[i].c;
}
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);
}
void kruskal()
{
    int i,j,cx,cy,nrsel;
//ordonez muchiile crescator dupa cost
    ///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])
        {
            nrsel++;
            A[nrsel]=i;
            cost+=G[i].c;
            //unificam comp 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 afisare()
{
    int i;
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(i=1; i<=n-1; i++)
        fout<<G[A[i]].x<<' '<<G[A[i]].y<<'\n';
}
bool compar(Muchie a, Muchie b)
{
    return a.c<b.c;
}