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

using namespace std;

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

    return (a[2] - b[2]);
}

///Prim aalgoritmus
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int N, M, **lista;
    //static int lista[m][3];
    int dots = 2,el = 1, result;
    int **adj, *L;
    //static int adj[n-1][2] = {0}, L[n] = {0};
    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(M * sizeof(int*));
    for(int i = 0; i < M; ++i)
        adj[i] = (int*)malloc(2 * sizeof(int));

    L = (int*)calloc(M, 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;
}