#include <bits/stdc++.h>
#define NMAX 200002
#define MMAX 400002

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

struct muchie
{
    int x, y, c;
    friend bool operator < (muchie a, muchie b);
}apm[NMAX];

int n, m, costmin;
int tata[NMAX];
int h[NMAX]; ///h[x] = inaltimea arborelui cu radacina x

priority_queue <muchie> heap;

int Find(int x);
void Union(int x, int y);
void citire();
void kruskal();
void afisare();
bool operator < (muchie a, muchie b)
{
    return a.c > b.c;
}

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

void afisare()
{
    int i;

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

void kruskal()
{
    muchie aux;
    int rx, ry, nrsel = 0;

    while(nrsel < n-1)
    {
        aux = heap.top();
        heap.pop();

        rx = Find(aux.x);
        ry = Find(aux.y);

        if(rx != ry)
        {
            costmin += aux.c;
            apm[++nrsel] = aux;
            Union(rx, ry);
        }
    }
}

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

int Find(int x) ///determina radacina lui x
{
    int rx, ry, y;
    rx = x;
    while(tata[rx]) rx = tata[rx];
    ///rx este radacina arborelui
    ///compresez drumul de la x la rx
    ///fiecare nod de pe acest drum devine fiu a lui rx

    while(tata[x] && tata[x] != rx)
    {
        y = tata[x];
        tata[x] = rx;
        x = y;
    }

    return rx;
}

void Union(int x, int y) ///reuneste arborele in care se afla x cu arborele in care se afla 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]) ///ry devine fiul lui rx
            tata[ry] = rx;
        else ///egalitate
            {tata[ry] = rx; h[rx]++;}
    }
}