#include <fstream>
#define NMAX 200002
#define MMAX 400002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
int tata[NMAX];///vectorul de tati ai arborilor care reprezinta partitia
int inaltime[NMAX];
struct Muchie
{
    int x,y,c;
};
Muchie H[MMAX],A[MMAX];
void Union(int i, int j);
int Find(int i);
void inserare(Muchie H[], int& n, int x);
void afisare();
void combinare(int poz);
void creare();
Muchie ExtragereMin();
void kruskal();
int main()
{

    creare();
    kruskal();
    afisare();
    return 0;
}
void kruskal()
{
    int cx,cy,nr;
    Muchie minim;
    for (nr=0; nr<n-1;)
    {
        minim=ExtragereMin();
        cx=Find(minim.x);
        cy=Find(minim.y);
        if (cx!=cy)
        {
            A[nr++]=minim;
            Union(cx,cy);
        }
    }
}
void Union(int i, int j)
///reuneste arborele cu radacina i cu arborele cu radacina j
{
    if(inaltime[i]<inaltime[j])
        tata[i]=j;
    else
    {
        tata[j]=i;
        if(inaltime[i]==inaltime[j]) inaltime[i]++;
    }
}
int Find(int i)
///determina radacina arborelui din care face parte i
{
    int r=i, x, t;
    while(tata[r]) r=tata[r];
    ///compresez drumul de la i la r
    x=i;
    while(x!=r)
    {
        t=tata[x];
        tata[x]=r;
        x=t;
    }
    return r;
}


void inserare(int H[], int& n, int x)
{
    int fiu=++n,tata=fiu/2;
    ///caut locul lui x retrogradand succesiv elementele mai mari de pe drumul de la pozitia lui x catre radacina
    while(tata&& H[tata]>x)
    {
        H[fiu]=H[tata];
        fiu=tata;
        tata=fiu/2;
    }
    H[fiu]=x;
}

void afisare()
{
    int i;
    int cost=0;
    for(i=0; i<n-1; i++) cost+=A[i].c;
    fout<<cost<<'\n'<<n-1<<'\n';
    for(i=0; i<n-1; i++) fout<<A[i].x<<" "<<A[i].y<<'\n';
}
void combinare(int poz)
{
    ///nodul de pe pozitia poz se va combina cu minheapurile cu radacinile 2*poz si 2*poz+1- acestea sunt deja construite
    Muchie x=H[poz];
    int tata=poz, fiu=2*poz;
    while(fiu<=m)
    {
        if(fiu+1<=m && H[fiu+1].c<H[fiu].c)
            fiu++;
        if(H[fiu].c<x.c)
        {
            H[tata]=H[fiu];
            tata=fiu;
            fiu=2*tata;
        }
        else
            break;
    }
    H[tata]=x;
}
void creare()
///O(n)
{
    int i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        fin>>H[i].x>>H[i].y>>H[i].c;
    for(i=m/2; i>=1; i--)
        combinare(i);
}
Muchie ExtragereMin()
{
    Muchie minim=H[1];
    H[1]=H[m];
    m--;
    combinare(1);
    return minim;
}