#include <cstdio>
#include <cstring>
#include <algorithm>

#define NMAX 200005
#define MMAX 400005
using namespace std;

struct muchie
{
    int x,y,c;
} a[MMAX], apm[NMAX];

int n, m, cost_min;
int t[NMAX], dim[NMAX];

void citire();
void kruskal_apm();
void afisare();
bool cmp(muchie m1, muchie m2) {return m1.c<m2.c;}
void join(int x, int y);
int comp_dif(int x, int y);
void afisare();

int main()
{
    citire();
    kruskal_apm();
    afisare();
    return 0;
}
void citire()
{

    muchie x;
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i=1; i<=m; ++i)
    {
        scanf("%d %d %d", &x.x, &x.y, &x.c);
        a[i] = x;
    }
}

void kruskal_apm()
{
    int nrm = 1, i = 2;
    memset(dim,1,sizeof(dim));
    sort(a+1, a+1+m, cmp);

    apm[1] = a[1];
    cost_min = a[1].c;
    join(a[1].x, a[1].y);

    while (nrm < n-1)
    {
        while (!comp_dif(a[i].x,a[i].y)) ++i;
        apm[++nrm] = a[i];
        cost_min += a[i].c;
        join(a[i].x, a[i].y);
    }
}
void join(int x, int y)
{
    while (t[x]) x = t[x];
    while (t[y]) y = t[y];

    if (dim[x] > dim[y]) t[y] = x;
    else t[x] = y;
}
int comp_dif(int x, int y)
{
    int aux;
    int a = x;
    int b = y;

    while (t[x]) x = t[x];
    while (t[y]) y = t[y];

    while (t[a] && t[a] != x)
    {
        aux = t[a];
        t[a] = x;
        a = aux;
    }
    while (t[b] && t[b] != y)
    {
        aux = t[b];
        t[b] = y;
        b = aux;
    }
    if (x != y) return 1;
    return 0;
}
void afisare()
{
    printf("%d\n%d\n", cost_min, n-1);
    for (int i = 1; i<n; ++i)
        printf("%d %d\n", apm[i].x, apm[i].y);
}