#include <iostream>
#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]);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out", "w", stdout);
    int **elek, n, m;
    int **adj;

    cin >> n >> m;
    elek = new int* [m];

    for (int i = 0 ; i < m ; i++)
    {
        elek[i] = new int [3];
        cin >> elek[i][0] >> elek[i][1] >> elek[i][2];
    }

    adj = new int* [m];
    for(int i = 0; i < m; ++i){
        adj[i] = new int [2];
    }

    qsort(elek ,m, sizeof(int*), cmp);

    int halm[n+1];

    for (int i = 1 ; i <= n ; i++)
    {
        halm[i] = i;
    }

    int k = n-1, el = 0, s = 0;
    int index = 0;

    while (k)
    {
        int x = elek[el][0];
        int y = elek[el][1];

        if (halm[x] != halm[y])
        {
            int r = halm[x];
            int g = halm[y];
            //cout << x << " " << y << "\n";
            adj[index][0] = x;
            adj[index++][1] = y;
            for (int i = 1 ; i <= n ; i++)
            {
                if (halm[i] == r)
                    halm[i] = g;
            }

            s += elek[el][2];
            k--;
        }
        el++;
    }

    cout << s << "\n" << index << "\n";
    for(int i = 0; i < index; ++i){
        cout << adj[i][0] << " " << adj[i][1] << "\n";
    }

    for(int i = 0; i < m; i++){
        delete [] elek[i];
    }
    delete [] elek;
    for(int i = 0; i < el; ++i){
        delete [] adj[i];
    }
    delete [] adj;

    return 0;
}