#include <iostream>
#include <fstream>
#include <queue>
#define NMAX 200002
#define MMAX 400002
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");


int n,m;
int tata[NMAX];
int h[NMAX];
struct muchie
{
    int x,y,c;
    friend bool operator < (muchie a, muchie b);
};
priority_queue<muchie> H;
muchie apm[NMAX];
int costmin;
bool operator < (muchie a, muchie b)
{
    return a.c>b.c;
}

int Find(int x)
{
    int rx,y;
    ///determin rad arborelui
    rx=x;
    while(tata[rx]!=0)
        rx=tata[rx];

        //rx e radacina
        ///compresez drumul de la x la rx;
        ///fiecare nod de pe acest drum devine fiu al lui rx
        while (tata[x] && tata[x]!=rx)
        {
            y=tata[x];
            tata[x]=rx;
            x=y;
        }

}

void Union(int x, int y)
{
    int rx,ry;
    rx=Find(x);
    ry=Find(y);
    if (h[rx]<h[ry])
        ///rx devine fiul lui ry
        tata[rx]=ry;
    else
        if (h[ry]<h[rx])
            tata[ry]=rx;
    else ///egal
    {
        tata[ry]=rx;
        h[rx]++;
    }

}

void citire()
{
    int i;
 fin>>n>>m;
 muchie aux;
 for (i=0; i<m; i++)
    {
        fin>>aux.x>>aux.y>>aux.c;
        H.push(aux);
    }
}

void kruskal()
{
    muchie aux;
    int nrsel;
    nrsel=0;
    int rx,ry;
    while (nrsel<n-1)
    {
        aux=H.top();
        H.pop();
        rx=Find(aux.x);
        ry=Find(aux.y);
        if (rx!=ry)
        {
            costmin+=aux.c;
            apm[++nrsel]=aux;
            Union(rx,ry);
        }
    }
}

void afisare()
{
    int i;
    fout<<costmin<<'\n';
    fout<<n-1<<'\n';
    for (i=1; i<n; i++)
    {
        fout<<apm[i].x<<' '<<apm[i].y<<'\n';
    }
}

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}