#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 200001
using namespace std;
struct muchie
{
    int x,y,c;
}aux;

struct solutie
{
    int x,y;
}auxSol;//vectorul in care retinem muchiile arborelui solutie
vector< muchie > V;
vector<solutie> S;
vector<int> L;
int n,m;


void citire()
{
    int c,x,y;
    cin>>n>>m;
    V.push_back(aux);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        aux.x=x; aux.y=y; aux.c=c;
        V.push_back(aux);
    }
}
int comp(muchie i,muchie j){
    return (i.c<j.c);
}
void Kruskal()
{
    //L[i] reprezinta arborele din care face parte nodul i
    int i,j,ctotal=0,nrm=0;      // numarul muchiilor selectate e 0

    for(i=0; i<=n; i++){ // initial fiecare nod face parte dintr-un arbore separat
        L.push_back(i);
        S.push_back(auxSol);
    }


    i=1;// plecam de la V[1]
    while(nrm<n-1)
    {
        if( L[ V[i].x ] != L[ V[i].y ] )// daca nu se formeaza ciclu
        {
            nrm++;//creste numarul de muchii selectate
            //cout<<V[i].x<<' '<<V[i].y<<'\n';
            S[nrm].x=V[i].x;
            S[nrm].y=V[i].y;
            ctotal+=V[i].c;
            //unificarea arborilor
            int a,b;//reprezinta 2 arbori ce urmeaza a fi unificati
            a=L[ V[i].x ];
            b=L[ V[i].y ];
            for(j=1; j<=n; j++)
                if(L[j]==a)
                    L[j]=b;
        }
        i++;
    }
    //afisare
    cout<<ctotal<<'\n';
    cout<<nrm<<'\n';
    for(i=1;i<=nrm;i++)
        cout<<S[i].x<<' '<<S[i].y<<'\n';

}

int main()
{
    freopen("kruskal.in","rt",stdin);
    freopen("kruskal.out","wt",stdout);
    citire();
    sort(&V[1], &V[m+1] ,comp);     //ordonarea crescatoare a elementelor din V in functie de cost
    Kruskal();
    return 0;
}