#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200002
#define MMAX 400002

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

int n,m;
long long int cmin;
int nrsel;
struct muchie {int x,y,c;};
muchie g[MMAX];
int tata[NMAX];
int apm[MMAX]; //apm[i]=nr de ordine al celei de a i muchie selectate
int marime[NMAX]; //marime[i]=marimea multimii cu reprezentantul i

void citire();

bool compar(muchie a, muchie b)
{
    return a.c<b.c;
}

void kruskal();
void afisare();

int gaseste(int x)
{
    if(tata[x]==x) //adica e radacina, si deci, reprezentantul multimii
        return x;
    tata[x]=gaseste(tata[x]);
    return tata[x];
}

void uneste(int x,int y)
{
    //unesc multimile cu reprezentantii x si y (ptc am apelat functia deja cu reprezentantii multumilor din care faceau parte varfurile
    if(x!=y) //daca reprezentantii sunt diferiti
        {
         if(marime[x]<marime[y]) //conventie ca mereu lipim de arborele mai mare cel mic
            swap(x,y);
         tata[y]=x;
         marime[x]+=marime[y];
        }
}
int main()
{
    citire();
    sort(g+1,g+m+1,compar);
    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 kruskal()
{
    int i,a,b;
    //initializare parinti;
    for(i=1; i<=n; i++)
        {tata[i]=i; marime[i]=1;} //fiecare are ca reprez pe el insusi
    nrsel=0; //nr muchii selectate
    i=1;
    while(nrsel<n-1)
        {
         a=gaseste(g[i].x);
         b=gaseste(g[i].y);
         if(a!=b) //daca grupa din care face parte x nu are acelasi reprez (a) cu grupa din care face parte y (b), le pot uni
            {
             nrsel++;
             uneste(a,b); //unesc multimile care au ca reprezentanti pe a si b
             cmin+=g[i].c;
             apm[nrsel]=i;
            }
         i++;
        }
}

void afisare()
{
    int i;
    fout<<cmin<<'\n';
    fout<<nrsel<<'\n';
    for(i=1; i<=nrsel; i++)
        fout<<g[apm[i]].x<<' '<<g[apm[i]].y<<'\n';

}