#include <fstream>
#include <cstdio>
#include <algorithm>
#define NMAX 200005
#define MMAX 400010

using namespace std;

FILE*fin;
ofstream fout("apm.out");

struct muchie{
int x, y, cost;
} v[NMAX];

int n, m, h[NMAX], tata[NMAX], sol[NMAX],cost;
void citire();
void kruskal();
int Find(int x);
void Union(int x, int y);
void afisare();

int criteriu(muchie A, muchie B)
{
    if(A.cost > B.cost)
        return 0;
    return 1;
}

int main()
{
    citire();
    sort(v + 1, v + n + 1, criteriu);
    kruskal();
    afisare();
    return 0;
}

void citire()
{
    int i;
    fin = freopen("apm.in", "r", stdin);
    fscanf(fin, "%d%d", &n, &m);
    for(i = 1; i <= m; i++)
        fscanf(fin, "%d%d%d", &v[i].x, &v[i].y, &v[i].cost);
}

void kruskal()
{
    int i, nrsel = 1, adv = 0, rx, ry, nrsol = 0;
    muchie p;
    while(nrsel <= n - 1)
    {
        ++adv;
        p = v[adv];
        rx = Find(p.x);
        ry = Find(p.y);
        if(rx != ry)
        {
            Union(rx, ry);
            sol[++nrsol] = adv;
            cost += p.cost;
            ++nrsel;
        }
    }

}

int Find(int x)
{
    int rx = x, y;
    while(tata[rx]) rx = tata[rx];
    while(x != rx)
    {
        y = tata[x];
        tata[x] = rx;
        x = y;
    }
    return rx;
}

void Union(int x, int y)
{
    if(h[x] > h[y])
    {
        tata[y] = x;
    }
    else if(h[x] < h[y])
    {
        tata[x] = y;
    }
        else{
            tata[y] = x;
            h[x]++;
        }
}

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