#include<bits/stdc++.h>

#define Nmax 200005
#define Mmax 400005

using namespace std;

int Cost[Mmax], From[Mmax], To[Mmax], ind[Mmax], Sol[Nmax];
int N, M, APM_sol;
int Dad[Nmax], Rang[Nmax];

bool cmp(int i, int j)
{
    return Cost[i] < Cost[j];
}

void Read()
{
    freopen("apm.in", "r", stdin);
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; ind[i] = i, ++ i)
        scanf("%d %d %d", &From[i], &To[i], &Cost[i]);
    sort(ind + 1, ind + 1 + M, cmp);
}

void Write()
{
    freopen("apm.out", "w", stdout);
    printf("%d\n%d\n", APM_sol, N - 1);
    for(int i = 1; i < N; ++ i)
        printf("%d %d\n", From[Sol[i]], To[Sol[i]]);
}

int Find(int X)
{
    if(Dad[X] == X)
        return X;
    return (Dad[X] = Find(Dad[X]));
}

void Union(int X, int Y)
{
    if(Rang[X] > Rang[Y])
        Dad[Y] = X;
    else
        Dad[X] = Y;
    if(Rang[X] == Rang[Y])
        Rang[Y] ++;
}

void Kruskal()
{
    int DIM = 0;

    for(int i = 1; i <= N; ++ i) {
        Rang[i] = 1;
        Dad[i] = i;
    }

    for(int i = 1; i <= M; ++ i) {
        int X = From[ind[i]], Y = To[ind[i]];
        if(Find(X) != Find(Y)) {
            Union(Dad[X], Dad[Y]);
            APM_sol += Cost[ind[i]];
            Sol[++ DIM] = ind[i];
        }
    }

    Write();
}

int main()
{
    Read();
    Kruskal();
    return 0;
}