#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
typedef struct{long int u,v,c;} muchie;
long int v,u,n,m,i,j;
long int S; //costul arborelui
long int r[200000];
vector <muchie> e;
vector <muchie> A; //arborele partial de cost min
muchie x;

void Sort()
{
    for (i=0; i<m-1; i++)
        for (j=i; j<m; j++)
            if (e[i].c>e[j].c)
            {
                x=e[i];
                e[i]=e[j];
                e[j]=x;
            }
}

int main()
{
    f>>n>>m;
    for (i=0; i<m; i++) //citire
    {
        f>>x.u>>x.v>>x.c;
        e.push_back(x);
    }
    for (i=1; i<=n; i++)
        r[i]=i; //initial fiecare varf este un arbore
    Sort(); //sorteaza muchiile crescator

    for (i=0; i<e.size(); i++)
        if (r[e[i].u]!=r[e[i].v])
        {
            A.push_back(e[i]);
            S+=e[i].c;
            //Union (u,v) -- schimbam reprezentatii
            for (j=1; j<=n; j++)
                if (r[j]==r[e[i].u])
                    r[j]=r[e[i].v];
            if (A.size()==n-1)
                break;
        }
    g<<S<<'\n';
    g<<n-1<<'\n';
    for (i=0; i<A.size(); i++)
        g<<A[i].u<<" "<<A[i].v<<" "<<'\n';
    return 0;
}