#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

void kiir(int **a, int n, int m)
{
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j)
            cout << a[i][j] << " ";
        cout << '\n';
    }
    cout << '\n';
}

int cmp(const void *p1, const void * p2)
{
    int *a = *(int**)p1;
    int *b = *(int**)p2;

    if(a[2] > b[2]) return 1;
    else if(a[2] < b[2]) return -1;
    else return 0;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int N, M, **lista;
    int dots = 2,el = 1, result;
    int **adj, *L;
    int X, Y, C;
    cin >> N >> M;

    lista = (int**)malloc(M * sizeof(int*));
    for(int i = 0; i < M; ++i)
        lista[i] = (int*)malloc(3 * sizeof(int));

    adj = (int**)malloc((N-1) * sizeof(int*));
    for(int i = 0; i < N-1; ++i)
        adj[i] = (int*)malloc(2 * sizeof(int));

    L = (int*)calloc(N, sizeof(int));

    for(int i = 0; i < M; ++i){
        cin >> X >> Y >> C;
        lista[i][0] = X;
        lista[i][1] = Y;
        lista[i][2] = C;
    }

    qsort(lista, M, sizeof(int*), cmp);

    X = 0;
    result = lista[0][2];
    adj[X][0] = lista[0][0];
    adj[X++][1] = lista[0][1];
    for(int i = 1; i < M; ++i)
    {
        el++;
        if((L[lista[i][0]] == 0) || (L[lista[i][1]] == 0)){
            dots++;
            result += lista[i][2];
            adj[X][0] = lista[i][0];
            adj[X++][1] = lista[i][1];
            L[lista[i][0]]++;
            L[lista[i][1]]++;
        }
        else if(el == dots){
            el--;
        }
        if(dots == N) break;
    }

    cout << result << '\n' << el << '\n';
    for(int i = 0; i < el; ++i){
        cout << adj[i][0] << ' ' << adj[i][1] << '\n';
    }

    for(int i = 0; i < M; ++i)
        free(lista[i]);
    free(lista);
    for(int i = 0; i < M; ++i)
        free(adj[i]);
    free(adj);
    free(L);

    return 0;
}