#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 100001
using namespace std;
struct muchie
{
    int x,y,c;
}aux;
vector<muchie> V;
vector<int> niv, T;       //se folosesc pentru simularea arborelui
int n,m;

void citire();
int comp(muchie i, muchie j);
int root(int x);
void unificare(int rArbx, int rArby);
void Kruskal();

int main()
{
    freopen("apm.in","rt",stdin);
    freopen("apm.out","wt",stdout);
    citire();
    sort(&V[1], &V[m+1] ,comp);     //ordonarea crescatoare a elementelor din V in functie de cost
    Kruskal();
    return 0;
}
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);
}
int root(int x)
{
    while(x != T[x])
        x=T[x];
    return x;
}
void unificare(int rArbx, int rArby)
{
    if(niv[rArbx] > niv[rArby])
        T[rArby] = rArbx;
    else if(niv[rArbx] <= niv[rArby])
        T[rArbx] = rArby;
    if(niv[rArbx] == niv[rArby])
        niv[rArby]++;
}
void Kruskal()
{
    int muchie,j,cTotal=0,nrM=0, rootx, rooty;        //numarul muchiilor selectate e 0
    vector<pair<int, int> >S;                       //vectorul in care retinem muchiile arborelui solutie
    for(int i=0; i<=n; ++i)                              //initial fiecare nod face parte dintr-un arbore separat
        T.push_back(i);
    niv.assign(n+1, 1);                            //initial toate nodurile sunt pe primul nivel
    muchie=1;                                        //plecam de la V[1]
    while(nrM<n-1)
    {
        rootx = root(V[muchie].x);
        rooty = root(V[muchie].y);
        if( rootx != rooty)                          //daca nu se formeaza ciclu
        {
            unificare(rootx, rooty);                 //unificarea arborilor
            nrM++;                                   //creste numarul de muchii selectate
            S.push_back(make_pair(V[muchie].x, V[muchie].y));
            cTotal += V[muchie].c;
        }
        muchie++;
    }
    //afisare
    cout<<cTotal<<'\n';
    cout<<nrM<<'\n';
    for(int i=0; i<nrM; ++i)
        cout<<S[i].first<<' '<<S[i].second<<'\n';
}